Skip to page content Home     Posts     CV     Contact     People

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.