Iterated function

In mathematics, an iterated function is a function that is obtained by composing another function with itself two or several times. The process of repeatedly applying the same function is called iteration. In this process, starting from some initial object, the result of applying a given function is fed again into the function as input, and this process is repeated.

For example, on the image on the right:

Iterated functions are studied in computer science, fractals, dynamical systems, mathematics and renormalization group physics.

The formal definition of an iterated function on a set X follows.

Let X be a set and f: X → X be a function.

Defining f ⁿ as the n-th iterate of f, where n is a non-negative integer, by: $${\displaystyle f^{0}~{\stackrel {\mathrm {def} }{=}}~\operatorname {id} _{X}}$$ and $${\displaystyle f^{n+1}~{\stackrel {\mathrm {def} }{=}}~f\circ f^{n},}$$

where id_X is the identity function on X and (f ${\displaystyle \circ }$ g)(x) = f (g(x)) denotes function composition. This notation has been traced to and John Frederick William Herschel in 1813. Herschel credited Hans Heinrich Bürmann for it, but without giving a specific reference to the work of Bürmann, which remains undiscovered.

Because the notation f ⁿ may refer to both iteration (composition) of the function f or exponentiation of the function f (the latter is commonly used in trigonometry), some mathematicians^{[citation needed]} choose to use ∘ to denote the compositional meaning, writing f^∘n(x) for the n-th iterate of the function f(x), as in, for example, f^∘3(x) meaning f(f(f(x))). For the same purpose, f ^[n](x) was used by Benjamin Peirce whereas Alfred Pringsheim and Jules Molk suggested ⁿf(x) instead.