Franklin Pezzuti Dyer’s Blog

Iterated Functions

2017 Jan 12

Have you ever wonder what happens when you plug a function into itself, and then do it again, and again, over and over and over again?

Let’s start with a bit of notation. The composition of two functions \(f\) and \(g\) is denoted \((f\circ g)\). Let’s call the composition of a function \(f\) with itself the second iterate of \(f\) and, for the sake of compactness, denote it by \(f^2\) rather than \((f\circ f)\). Similarly, we will replace \((f\circ f\circ f)\) with \(f^3\) and call it the third iterate of \(f\), and so on. Also, since \(f^{-1}\) denotes the inverse of \(f\), let \(f^{-n}\) denote the nth iterate of the inverse of \(f\). Finally, by convention, we will let \(f^0(x)=x\).

After playing around with the mechanics of these functions, one notices many properties similar to those of exponents. For example, the composition \((f^m\circ f^n)\) is equal to \(f^{m+n}\). Additionally, if the mth iterate of \(f\), \(f^m\), is iterated \(n\) times, the result is \(f^{mn}\).

Now let’s look at something a little less abstract. Consider the function \(f(x)=x+1\). We can see easily that each time we iterate this function, we will be adding 1 to our previous output, so we can state that \(f^n(x)=x+n\). Note that this result holds even for negative \(n\), because the inverse of \(f\) is \(f^{-1}(x)=x-1\).

Consider the function \(f(x)=x+2\). The first couple iterates of this function are
\[f^2(x)=(x+2)+2=x+4\]
\[f^3(x)=(x+4)+2=x+6\]
\[f^4(x)=(x+6)+2=x+8\]
It is easy to see that \(f^n(x)=x+2n\). In fact, I believe that we can come up with a general formula for any function of the form \(f(x)=x+c\). If we iterate it but leave \(c\) as an arbitrary constant, we can notice enough of a pattern to design a formula:
\[f^2(x)=(x+c)+c=x+2c\]
\[f^2(x)=(x+2c)+c=x+3c\]
\[...\]
\[f^n(x)=x+cn\]

That function wasn’t very challenging to work with. Let’s try a function of the form \(f(x)=cx\). By iterating this, we can see that
\[f^2(x)=c(cx)=c^2x\]
\[f^2(x)=c(c^2x)=c^3x\]
\[...\]
\[f^n(x)=c^nx\]

Finally, let’s try finding a formula for linear functions of the form \(f(x)=cx+d\) where \(d\) is also a constant.
\[f^2(x)=c(cx+d)+d=c^2x+cd+d\]
\[f^2(x)=c(c^2x+cd+d)=c^3x+c^2d+cd+d\]
\[...\]
\[f^n(x)=c^nx+c^{n-1}d+c^{n-2}d+...+c^2d+cd+d\]

We can manipulate this result to make it into a closed-form formula.
\[f^n(x)=c^nx+d(c^{n-1}+c^{n-2}+...+c^2+c+1)\]

It is obvious now that \(c\) is forming the summation of a geometric series. The formula for a summation of the form \(1+a+a^2+...+a^n\) is \(\frac{a^{n+1}-1}{a-1}\), so we can condense our formula to
\[f^n(x)=c^nx+d(\frac{c^n-1}{c-1})\]

Analogous formulas exist for functions of other types. For example, if \(f(x)=x^c\), then
\[f^2(x)=(x^c)^c=x^{c^2}\]
\[f^3(x)=(x^{c^2})^c=x^{c^3}\]
\[...\]
\[f^n(x)=x^{c^n}\]

and if \(f(x)=cx^d\), then
\[f^2(x)=c(cx^d)^d=c^{d+1}x^{d^2}\]
\[f^3(x)=c(c^{d+1}x^{d^2})^d=c^{d^2+d+1}x^{d^3}\]
\[...\]
\[f^n(x)=c^{1+d+d^2+...+d^{n-1}}x^{d^n}\]
\[f^n(x)=c^{\frac{d^n-1}{d-1}}x^{d^n}\].

This is very interesting and I would like to revisit it later to try and find more types of functions that I can iterate.