## 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:
$f_1(x)=x^{\ln(x)}$
$f_2(x)=x^{\ln(x)+2}$
$f_3(x)=\ln(e^x+1)$
$f_4(x)=\ln(e^x+1)+1$
$f_5(x)=\frac{\ln(e^x+1)+\ln(e^x-1)}{2}$
$f_6(x)=x+\ln(e^x+2)$

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
$g(x)=x+\frac{\beta}{\alpha-1}$
$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}$
and
$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
$f(x)=2x^2-1$
$g(x)=\arccos x$
$h(x)=2x$
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,
$\cosh(ix)=\cos(x)$
and
$-i\operatorname{arccosh}(x)=\arccos(x)$
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
$f(x)=x^3+3x^2+3x$
then we may write
$f(x)=(x+1)^3-1$
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
$f(x)=\frac{1/\alpha}{\beta\frac{1/\alpha}{x}+1}$
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}}$
or
$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
$F(x)=f(x+k)-k=\frac{(\alpha-k)x-k^2+(\alpha-\gamma)k+\beta}{x+k+\gamma}$
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
$-k^2+(\alpha-\gamma)k+\beta=0$
$k=\frac{\alpha-\gamma\pm \sqrt{(\alpha-\gamma)^2+4b}}{2}$
So, if we set $$k$$ equal to that value, we have
$F(x)=\frac{(\alpha-k)x}{x+k+\gamma}$
or
$F(x)=\frac{x}{\frac{1}{\alpha-k}x+\frac{\gamma+k}{\alpha-k}}$
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
$f_1(x)=x^{\ln(x)}$
To iterate this, one must notice that
$x^{\ln(x)}=e^{\ln(x)^2}$
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:
$f_2(x)=x^{\ln(x)+2}$
We may rewrite $$f_2$$ as
$f_2(x)=e^{\ln(x)^2+2\ln(x)}$
or
$f_2(x)=e^{(\ln(x)+1)^2-1}$
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
$f_3(x)=\ln(e^x+1)$
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:
$f_4(x)=\ln(e^x+1)+1$
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)$
or
$f_4^{\circ n}(x)=\ln\bigg(e^{x+n-1}+\frac{e^n-1}{e-1}\bigg)+1$

Now the fifth function:
$f_5(x)=\frac{\ln(e^x+1)+\ln(e^x-1)}{2}$
This can be rewritten as
$f_5(x)=\frac{\ln((e^x+1)(e^x-1))}{2}=\frac{\ln(e^{2x}-1)}{2}$
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:
$f_6(x)=x+\ln(e^x+2)$
This can be written as
$f_6(x)=\ln(e^{2x}+2e^x)=\ln((e^x+1)^2-1)$
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.