Skip to page content Home     Posts     CV     Contact     People

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