Deriving a general formula for the nth composition of a function

Question

Let $f^n(x)$ denote the nth composition of $f(x)=\dfrac{ax+b}{bx+a}$. Find an explicit expression for $f^n(x) $.

Insofar, I noticed on taking the first 3 compositions of $f(x)$, the terms from the binomial expansion of $(a+b)^n$ seem to pop up, but I can't find a precise pattern or a way of proving this assertion via induction;

$f^2(x)=\dfrac{(a^2+b^2)x+2ab}{2abx+(a^2+b^2)}$

$f^3(x)=\dfrac{(a^3+3ab^2)x+(3a^2b+b^3)}{(b^3+3a^2b)x+(a^3+3ab^2)}$

$f^4(x)=\dfrac{(a^4+b^4+6a^2b^2)x+(4a^2b+4ab^2)}{(4a^2b+4ab^2)x+(a^4+b^4+6a^2b^2)}$

The nth composition of $f(x)$ will have the form $f(x)=\dfrac{Ax+B}{Bx+A}$ where A and B will contain the binomial coefficients of $(a+b)^n$ but how can I compute $A$ and $B$ here?

Answer 1

$f^n(x)=\dfrac{A_n x+B_n}{B_n x+A_n},$then $f(f^n(x))=\dfrac{(aA_n+b B_n)x+aB_n+bA_n}{(aB_n+bA_n)x+aA_n+B_n}.$

$P_n=\left(\begin{matrix}A_n & B_n \\ B_n & A_n\end{matrix}\right),P_{n+1}=P_n\left(\begin{matrix}a & b \\ b & a\end{matrix}\right).$Thus $P_n=\left(\begin{matrix}a & b \\ b & a\end{matrix}\right)^n$.

Consider $A=\left(\begin{matrix}a & b \\ b & a\end{matrix}\right)$. $|\lambda I-A|=(\lambda-a+b)(\lambda-a-b).\implies P^{-1}AP=\left(\begin{matrix}a-b & 0 \\ 0 & a+b\end{matrix}\right).$Here $P=\left(\begin{matrix}1 & 1 \\ -1 & 1\end{matrix}\right).$

Hence $P_n=A^n=P\left(\begin{matrix}(a-b)^n & 0 \\ 0 & (a+b)^n\end{matrix}\right)P^{-1}=\left(\begin{matrix}(a-b)^n/2+(a+b)^n/2 & -(a-b)^n/2+(a+b)^n/2 \\ -(a-b)^n/2+(a+b)^n/2 & (a-b)^n/2+(a+b)^n/2\end{matrix}\right).$

Answer 2

Functions like that are commonly used in complex dynamics. I'm assuming, by your use of $x$, that you're more interested in the real case, but a map of the form $z \mapsto \frac{az+b}{cz+d}$ is called a Möbius transformation, and there's a very interesting section on it in Alan F. Beardon's Iteration of Rational Functions, specifically Section 2.4 on Conjugacy, where the hint Trebor gave you as a comment is provided, with extra details.

There are little exercises in the end of each section that might guide you to the answers you're looking for, the main one obviously being the results of Exercise 2.4 (i) :

(i) Prove that any Möbius map is conjugate to one of the maps $z \mapsto az$, $z \mapsto z+a$ for a suitable value of $a$.

You can comfortably shift your focus to expressing the constant of this linear map using the $a,b,c,d$ of your function $f$, as from then you'll be able to iterate $f$ more easily.