Franklin’s Blog

A summary of functional iteration

2017 Nov 4

In this post, I will pose a few functional-iteration puzzles, rederive some useful iteration formulas, and discover a few new ones. All of the most important formulas are colored green, so that they will stand out.

Find a formula for the nth iterate of each of the following functions:

Before getting into any formulas or puzzles, I must remind the reader of the most important principle of functional iteration. If \(g,h\) are functions, then
\[\color{green}{(g^{-1}\circ h\circ g)^{\circ n}=g^{-1}\circ h^{\circ n}\circ g}\]
This fundamental property of function composition allows us to reduce difficult problems to easier ones. For example, consider the function
\[f(x)=\alpha x+\beta\]
In a previous post, I iterated this by forming a geometric series - however, it can be done in a much simpler way. Notice that we can rearrange this to obtain
\[f(x)=\alpha \bigg(x+\frac{\beta}{\alpha-1}\bigg)-\frac{\beta}{\alpha-1}\]
for \(\alpha\ne 1\). Then, if we define \(g\) and \(h\) as
\[h(x)=\alpha x\]
we can write
\[f(x)=(g^{-1}\circ h\circ g)(x)\]
and so
\[f^{\circ n}(x)=(g^{-1}\circ h\circ g)^{\circ n}(x)\]
\[f^{\circ n}(x)=(g^{-1}\circ h^{\circ n}\circ g)(x)\]
Now we have reduced this problem to finding the nth iterate of \(h\), which we can instantly say is
\[h^{\circ n}(x)=\alpha^n x\]
And now we may say that
\[\begin{align} f^{\circ n}(x) & = (g^{-1}\circ h^{\circ n}\circ g)(x) \\ & = h^{\circ n}\bigg(x+\frac{\beta}{\alpha-1}\bigg)-\frac{\beta}{\alpha-1} \\ & = \alpha^n\bigg(x+\frac{\beta}{\alpha-1}\bigg)-\frac{\beta}{\alpha-1} \\ & = \alpha^n x+\frac{\alpha^n -1}{\alpha-1}\beta \\ \end{align}\]
and our final formula is:
\[\color{green}{f(x)=\alpha x+\beta \implies f^{\circ n}(x)=\alpha^n x+\frac{\alpha^n -1}{\alpha-1}\beta}\]
Using the same method, one may derive this analogous formula:
\[\color{green}{f(x)=\beta x^\alpha \implies f^{\circ n}(x)=\beta^{\frac{\alpha^n -1}{\alpha-1}}x^{\alpha^n}}\]

Now I will move on to iterating a quadratic. Unfortunately, it seems that only a few specific types of quadratics can be effectively iterated. One rather obvious class of quadratic is the set of quadratics in the form
\[f(x)=\frac{(\alpha x+\beta)^2}{\alpha}-\frac{\beta}{\alpha}\]
Notice that we may let \(g(x)=ax+b\) and \(h(x)=x^2\) to discover that
\[f^{\circ n}(x)=\frac{1}{\alpha}(\alpha x+\beta)^{2^n}-\frac{\beta}{\alpha}\]
Before we make this into a final formula, I would like to rearrange \(f\) so that \(f\) is written in standard quadratic form:
\[\begin{align} f(x) &= \frac{(\alpha x+\beta)^2}{\alpha}-\frac{\beta}{\alpha} \\ &= \frac{\alpha^2 x^2+2\alpha\beta x+\beta ^2 }{\alpha}-\frac{\beta}{\alpha} \\ &= \alpha x+2\beta x+\frac{\beta ^2-\beta}{\alpha} \\ \end{align}\]
and, if we let \(2\beta=\gamma\),
\[f(x)=\alpha x+\gamma x+\frac{\gamma ^2-\gamma}{4\alpha}\]
\[f^{\circ n}(x)=\frac{1}{\alpha}\bigg(\alpha x+\frac{\gamma}{2}\bigg)^{2^n}-\frac{\gamma}{2\alpha}\]
and so we are ready for our third formula:
\[\color{green}{f(x)=\alpha x+\gamma x+\frac{\gamma ^2-\gamma}{4\alpha}\implies f^{\circ n}(x)=\frac{1}{\alpha}\bigg(\alpha x+\frac{\gamma}{2}\bigg)^{2^n}-\frac{\gamma}{2\alpha}}\]

There is one more special type of quadratic that can be readily evaluated, and it originates from the double-angle formula of the cosine function:
\[\cos 2\theta=2\cos^2\theta-1\]
This allows us to say that
\[\cos (2\arccos x)=2x^2-1\]
for all \(x\) with \(|x|\le 1\). Do you recognize this as being in the form \(g^{-1}\circ h\circ g\)? If we let
\[g(x)=\arccos x\]
then we may readily state that
\[f^{\circ n}(x)=\cos(2^n\arccos x)\]
However, this can be generalized. If we instead let
\[f(x)=\alpha x^2+\beta x+\frac{\beta^2-2\beta-8}{4\alpha}=\frac{2}{\alpha}\cos\bigg(2\arccos\frac{2\alpha x+\beta}{4}\bigg)-\frac{\beta}{2\alpha}\]
with \(g(x)=\arccos \frac{2\alpha x+\beta}{4}\) and \(h(x)=2x\), then we may say that
\[\color{green}{f(x)=\alpha x^2+\beta x+\frac{\beta^2-2\beta-8}{4\alpha}\implies f^{\circ n}(x)=\frac{2}{\alpha}\cos\bigg(2^n\arccos\frac{2\alpha x+\beta}{4}\bigg)-\frac{\beta}{2\alpha}}\]
However, this only works for a very small domain, since the inverse cosine function is defined only for inputs between \(-1\) and \(1\). But this is an easy fix - as a result of Euler’s famous formula linking the trigonometric functions to the complex exponential function,
which means that
\[\alpha x^2+\beta x+\frac{\beta^2-2\beta-8}{4\alpha}=\frac{2}{\alpha}\cosh\bigg(2\operatorname{arccosh}\frac{2\alpha x+\beta}{4}\bigg)-\frac{\beta}{2\alpha}\]
and, because of the symmetry of a parabola, we may extend this property past the domain of the inverse hyperbolic cosine function:
\[\alpha x^2+\beta x+\frac{\beta^2-2\beta-8}{4\alpha}=\frac{2}{\alpha}\cosh\bigg(2\operatorname{arccosh}\bigg|\frac{2\alpha x+\beta}{4}\bigg|\bigg)-\frac{\beta}{2\alpha}\]
and so, at last, we may complete our pair of iteration formulas for this type of quadratic:
\[\color{green}{f(x)=\alpha x^2+\beta x+\frac{\beta^2-2\beta-8}{4\alpha}\implies f^{\circ n}(x)=\frac{2}{\alpha}\cosh\bigg(2^n\operatorname{arccosh}\bigg|\frac{2\alpha x+\beta}{4}\bigg|\bigg)-\frac{\beta}{2\alpha}}\]

The two choices of \(g\) and \(h\) that I used to iterate these quadratics can also be used for other polynomials. For example, if
then we may write
and so, by choosing \(g(x)=x+1\) and \(h(x)=x^3\),
\[f^{\circ n}(x)=(x+1)^{3^n}-1\]
The method using multiple-angle formulas of the cosine function can also be used for other polynomials. In fact, polynomials that are in such a form are called chebyshev polynomials. The nth chebyshev polynomial is defined as the unique polynomial solution to the functional equation
\[T_n(\cos\theta)=\cos(n\theta),\forall \theta\]

This wonderful method can also be used to find iteration formulas for certain rational functions. For example, consider a rational function in the form
\[f(x)=\frac{x}{\alpha x+\beta}\]
This rational function can be rewritten as
and so, if we let \(g(x)=\frac{1/\alpha}{x}\) and \(h(x)=\beta x+1\) and use our second formula,
\[f^{\circ n}(x)=\frac{1/\alpha}{\beta^n\frac{1/\alpha}{x}+\frac{\beta^n-1}{\beta-1}}\]
\[f^{\circ n}(x)=\frac{x(\beta-1)}{\beta^n(\beta-1)+\alpha(\beta^n-1)x}\]
and so we have another useful formula:
\[\color{green}{f(x)=\frac{x}{\alpha x+\beta}\implies f^{\circ n}(x)=\frac{x(\beta-1)}{\beta^n(\beta-1)+\alpha(\beta^n-1)x}}\]
We can use this special case to write an iteration formula for any first degree rational function. Suppose that
\[f(x)=\frac{\alpha x+\beta}{x+\gamma}\]
Then let us define the function \(F\) as
for some \(k\). This is a helpful substitution to make, since \(F(x)=f(x+k)-k\) implies that
\[F^{\circ n}(x)=f^{\circ n}(x+k)-k\]
and so if we find an iteration formula for \(F\), we may find one for \(f\) as well. If we want \(F\) to be in the form that we already know how to iterate, we can choose \(k\) such that
or, by the quadratic formula,
\[k=\frac{\alpha-\gamma\pm \sqrt{(\alpha-\gamma)^2+4b}}{2}\]
So, if we set \(k\) equal to that value, we have
Now it is in the form that we already know how to iterate, and using the previous formula, we may immediately write
\[F^{\circ n}(x)=\frac{x\big(\frac{\gamma +k}{\alpha -k}-1\big)}{\big(\frac{\gamma +k}{\alpha -k}\big)^n\big(\frac{\gamma +k}{\alpha -k}-1\big)+\frac{1}{\alpha-k}\big(\big(\frac{\gamma+k}{\alpha-k}\big)^n-1\big)x}\]
and, since \(F^{\circ n}(x)=f^{\circ n}(x+k)-k\), we have that \(f^{\circ n}(x)=F^{\circ n}(x-k)+k\), and so
\[f^{\circ n}(x)=\frac{(x-k)\big(\frac{\gamma +k}{\alpha -k}-1\big)}{\big(\frac{\gamma +k}{\alpha -k}\big)^n\big(\frac{\gamma +k}{\alpha -k}-1\big)+\frac{1}{\alpha-k}\big(\big(\frac{\gamma+k}{\alpha-k}\big)^n-1\big)(x-k)}+k\]
and so we have our final formula:
\[\color{green}{f(x)=\frac{\alpha x+\beta}{x+\gamma}\implies f^{\circ n}(x)=\frac{(x-k)\big(\frac{\gamma +k}{\alpha -k}-1\big)}{\big(\frac{\gamma +k}{\alpha -k}\big)^n\big(\frac{\gamma +k}{\alpha -k}-1\big)+\frac{1}{\alpha-k}\big(\big(\frac{\gamma+k}{\alpha-k}\big)^n-1\big)(x-k)}+k}\]
\[\color{green}{\text{where}\space\space\space\space k=\frac{\alpha-\gamma\pm \sqrt{(\alpha-\gamma)^2+4b}}{2}}\]

Now I will solve the puzzles that I posed at the beginning of the post. The first function was
To iterate this, one must notice that
and if we choose \(g(x)=\ln(x)\) and \(h(x)=x^2\), we have
\[f_1^{\circ n}(x)=e^{\ln(x)^{2^n}}\]

Now for the second function:
We may rewrite \(f_2\) as
and so, if we let \(g(x)=\ln(x)+1\) and \(h(x)=x^2\), we have
\[f_2^{\circ n}(x)=e^{(\ln(x)+1)^{2^n}-1}\]

The third function is
This problem is not difficult - in fact, I solved it in an earlier post. By letting \(g(x)=e^x\) and \(h(x)=x+1\), we have
The third function is
\[f_3^{\circ n}(x)=\ln(e^x+n)\]

The fourth function is very similar:
It can be rewritten as
\[f_4(x)=\ln(e\cdot e^x+e)\]
and if we let \(g(x)=e^x\) and \(h(x)=ex+e\) and use our second formula, we have
\[f_4^{\circ n}(x)=\ln\bigg(e^n\cdot e^x+\frac{e^n-1}{e-1}e\bigg)\]
\[f_4^{\circ n}(x)=\ln\bigg(e^{x+n-1}+\frac{e^n-1}{e-1}\bigg)+1\]

Now the fifth function:
This can be rewritten as
and so, by letting \(g(x)=e^{2x}\) and \(h(x)=x-1\),
\[f_5^{\circ n}(x)=\frac{\ln(e^{2x}-n)}{2}\]

Now for the sixth and final function:
This can be written as
and so, if we let \(g(x)=e^x+1\) and \(h(x)=x^2\),
\[f_6^{\circ n}(x)=\ln((e^x+1)^{2^n}-1)\]

That’s all for now! Let me remind you that my solutions to each of these problems were not instantaneous - the solutions you are seeing are polished, thought-out solutions. When trying these problems for the first time, my work was nowhere near as quick and tidy.