Iterations of $f(x)=\dfrac{ax+b}{cx+d}$

Consider $f(x)=\dfrac{ax+b}{cx+d}$, where $c\neq0$ and $f(x)$ is not equal to a constant. Is it necessarily true that $f^{[n]}(x)=f(x)$ for some natural number $n > 1$?

-
you want to find a,b,c,d such that there exists n such that for all x $f^{(n)}=f$? (where $f^{2)}(x)=f(f(x))$ – Amr Nov 19 '12 at 2:02
@Amr: as I interpret the question (looking at the three uses of the word "must") the question is whether all $f$ have the property that such an $n > 1$ exists. – Qiaochu Yuan Nov 19 '12 at 2:09
I think that he might not want your counterexamples because he does not want c to be zero – Amr Nov 19 '12 at 2:10
@Amr: ah, I didn't catch that. – Qiaochu Yuan Nov 19 '12 at 2:43

Consider $f(x)=\frac{x}{x+1}$. Then $f^{[n]}(x)=\frac{x}{nx+1}$.

If this is true for some $n$ (and it is for $n=1$) then \begin{align}f^{[n+1]}(x)&=\frac{\frac{x}{x+1}}{n\frac{x}{x+1}+1}\\ &=\frac{x}{nx+(x+1)}\\ &=\frac{x}{(n+1)x+1}\end{align} And so by induction $f^{[n]}(x)=\frac{x}{nx+1}$ for all $n\in\mathbb{N}$. This shows $f^{[n]}$ will never equal $f$ for $n\in\mathbb{N}$.

-
I avoided the connection between these "fractional linear transformations" and $2\times2$ matrices. But for a more enlightened understanding of the kind of function that you are studying, investigate that relationship. In particular convince yourself that a matrix for $f\circ g$ is the same as a matrix for $f$ multiplied with one for $g$, up to a possible constant multiple. – alex.jordan Nov 19 '12 at 6:58

Hint: for each function $f$ consider the corresponding matrix $$\begin{pmatrix} a & b\\ c & d\end{pmatrix}.$$ (Assume that matrices normalized so that $\det \begin{pmatrix} a & b\\ c & d\end{pmatrix} = 1$. The group of such matrices is denoted by $SL(2, \mathbb{R})$; the set of such maps $f$ is isomorphic to the group $SL(2, \mathbb{R})$. See http://en.wikipedia.org/wiki/SL2%28R%29 .)

Note that the matrix corresponding to the composition of functions $f$ and $g$ equals the product of matrices corresponding to functions $f$ and $g$. Thus the problem reduces to finding a matrix $A$ such that $A^n \neq A$ for every $n > 1$. We can choose $$A = \begin{pmatrix} \cos \psi & \sin \psi\\ -\sin \psi & \cos \psi\end{pmatrix},$$ where, $\psi$ is such that $\psi/\pi \notin {\mathbb Q}$; e.g. $\psi = 1$. Then $$A = \begin{pmatrix} \cos (\psi n) & \sin (\psi n)\\ -\sin (\psi n)& \cos (\psi n)\end{pmatrix} \neq A.$$

-
$\text{SL}_2(\mathbb{R})$ denotes the group of such matrices. $\text{PSL}_2(\mathbb{R})$ denotes a quotient of this group. – Qiaochu Yuan Nov 19 '12 at 2:43
@QiaochuYuan: OK, I clarified that. – Yury Nov 19 '12 at 3:15
@GerryMyerson: Thanks! I should be more careful with copy & paste ;-) – Yury Nov 19 '12 at 3:16

Let $f(x)=1/(x+1)$. Then $f(f(x))=(x+1)/(x+2)$, and $f(f(f(x)))=(2x+3)/(3x+5)$, the next few being $$\frac{3x+5}{5x+8},\frac{5x+8}{8x+13},\frac{8x+13}{13x+21},\frac{13x+21}{21x+34}.$$ As this series is continued, one gets coefficients which are adjacent Fibonacci numbers. This can be shown via induction. So no higher iteration of this $f(x)$ is the starting function $f(x)$, and in fact no terms in the series of iterations are equal as functions.

-