Finding the n-th Iterate

What this move does

Composing layer after layer becomes hopeless once $n$ is large. To write down $f^{(n)}(x)$ directly there are three common methods:

1. Guess, then prove: compute $f^{(1)},f^{(2)},f^{(3)}$, guess the pattern, and prove it by mathematical induction.
2. Fixed-point method: solve $f(x^{\ast })=x^{\ast }$. For a linear function $f(x)=ax+b$ we get $f(x)-x^{\ast }=a(x-x^{\ast })$. Seen from $x^{\ast }$ as the origin, $f$ just “multiplies by $a$”, so $f^{(n)}(x)-x^{\ast }=a^n(x-x^{\ast })$.
3. Bridge function (conjugation): find an invertible $\phi$ and a $g$ that is easy to iterate, with $f={\phi }^{-1}\circ g\circ \phi$. The $\phi \circ {\phi }^{-1}$ pairs in the middle cancel:

The table on the left of the workbench is the “slow way”: it really composes $n$ times. On the right is the formula. The “Formula = composition?” light is a check of the formula.

Work through one

A third common bridge is taking reciprocals: for $f(x)=\frac{x}{1+cx}$ we have $\frac{1}{f(x)}=\frac{1}{x}+c$. The reciprocal goes up by $c$ at each step, so $f^{(n)}(x)=\frac{x}{1+ncx}$. Choose $x/(1+cx)$ on the workbench to check.

When it fails

Practice