*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

nthiterate 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
This fundamental property of function composition allows us to reduce difficult problems to easier ones. For example, consider the function
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
for $\alpha\ne 1$. Then, if we define $g$ and $h$ as
we can write
and so
Now we have reduced this problem to finding the *nth* iterate of $h$, which we can instantly say is
And now we may say that
and our final formula is:
Using the same method, one may derive this analogous formula:

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 Notice that we may let $g(x)=ax+b$ and $h(x)=x^2$ to discover that Before we make this into a final formula, I would like to rearrange $f$ so that $f$ is written in standard quadratic form: and, if we let $2\beta=\gamma$, and and so we are ready for our third formula:

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: This allows us to say that 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 then we may readily state that However, this can be generalized. If we instead let with $g(x)=\arccos \frac{2\alpha x+\beta}{4}$ and $h(x)=2x$, then we may say that 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, and which means that and, because of the symmetry of a parabola, we may extend this property past the domain of the inverse hyperbolic cosine function: and so, at last, we may complete our pair of iteration formulas for this type of quadratic:

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

This wonderful method can also be used to find iteration formulas for certain rational functions. For example, consider a rational function in the form
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,
or
and so we have another useful formula:
We can use this special case to write an iteration formula for *any* first degree rational function. Suppose that
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
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,
So, if we set $k$ equal to that value, we have
or
Now it is in the form that we already know how to iterate, and using the previous formula, we may immediately write
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
and so we have our final formula:

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

Now for the second function: We may rewrite $f_2$ as or and so, if we let $g(x)=\ln(x)+1$ and $h(x)=x^2$, we have

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

The fourth function is very similar: It can be rewritten as and if we let $g(x)=e^x$ and $h(x)=ex+e$ and use our second formula, we have or

Now the fifth function: This can be rewritten as and so, by letting $g(x)=e^{2x}$ and $h(x)=x-1$,

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

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.