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
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:

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

Finally, let’s try finding a formula for linear functions of the form \(f(x)=cx+d\) where \(d\) is also a constant.

We can manipulate this result to make it into a closed-form formula.

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

Analogous formulas exist for functions of other types. For example, if \(f(x)=x^c\), then

and if \(f(x)=cx^d\), then

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