## 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.