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.