To find the general formula of $\overbrace{g(g(g(...g(x))}^\text{n}=g_n(x)=\frac{A_{n}.x+B_{n}}{C_{n}.x+D_{n}}$

Question

$$f(x)=\frac{1}{x+1}$$ $$f(f(x))=\frac{1}{\frac{1}{x+1}+1}=\frac{x+1}{x+2}$$ $$f(f(f(x)))=\frac{\frac{1}{x+1}+1}{\frac{1}{x+1}+2}=\frac{x+2}{2x+3}$$ It is easy to see that the general formula has relation with Fibonacci numbers and the general formula can be expressed as

$$\overbrace{f(f(f(...f(x))}^\text{n}=f_n(x)=\frac{F_{n-1}.x+F_{n}}{F_{n}.x+F_{n+1}}$$

where $F_{n}$ is Fibonacci numbers

If $$g(x)=\frac{ax+b}{cx+d}$$ then

$$\overbrace{g(g(g(...g(x))}^\text{n}=g_n(x)=\frac{A_{n}.x+B_{n}}{C_{n}.x+D_{n}}$$

What I tried:

$$g_n(g(x))=\frac{A_{n}.\frac{ax+b}{cx+d}+B_{n}}{C_{n}.\frac{ax+b}{cx+d}+D_{n}}$$

$$g_{n+1}(x)=\frac{A_{n}.\frac{ax+b}{cx+d}+B_{n}}{C_{n}.\frac{ax+b}{cx+d}+D_{n}}=\frac{(aA_{n}+cB_{n}).x+(bA_{n}+dB_n)}{(aC_{n}+cD_{n}).x+(b C_{n}+d D_{n})}$$

$$g_{n+1}(x)=\frac{A_{n+1}.x+B_{n+1}}{C_{n+1}.x+D_{n+1}}=\frac{(aA_{n}+cB_{n}).x+(bA_{n}+dB_n)}{(aC_{n}+cD_{n}).x+(b C_{n}+d D_{n})}$$

$$A_{n+1}=aA_{n}+cB_{n}$$ $$B_{n+1}=bA_{n}+dB_{n}$$ $$C_{n+1}=aC_{n}+cD_{n}$$ $$D_{n+1}=bC_{n}+dD_{n}$$ I got 4 equations but it seems very long to solve them. Is there an easy way to find the general formula of $g_n(x)$?

Thanks for advice and answers

UPDATE:

I believe $A_n,B_n,C_n,D_n $ should be expressed as sum of two exponential functions because we can do for $F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ where ϕ is the golden ratio .

Answer 1

It's actually one equation if you express it as a matrix: $$\begin{pmatrix}A_n&B_n\\C_n&D_n\end{pmatrix}=\begin{pmatrix}a&b\\c&d\end{pmatrix}^n$$

Putting the matrix $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ in Jordan normal form will make it easier to compute $A_n,B_n,C_n,D_n$.

Indeed, this method is one way to deduce Binet's formula for the Fibonacci numbers.

Answer 2

The group $PGL(2, \mathbb{R})$ of so-called linear fractional transformations (l.f.t.), namely the maps $$g: x \mapsto \frac{a x + b}{c x + d}, \qquad ad - bc \neq 0,$$ (where the condition simply excludes constant functions) under composition, has essentially the same product rule as matrix multiplication. A little more precisely, direct computation shows that the map $$GL(2, \mathbb{R}) \to PGL(2, \mathbb{R})$$ defined by $$\begin{pmatrix}a & b \\ c & d\end{pmatrix} \mapsto \left(x \mapsto \frac{a x + b}{c x + d}\right)$$ is a surjective homomorphism. The kernel of this map is just the subgroup of nonzero scalar matrices, i.e., if we scale a matrix by a nonzero constant $\lambda$, this doesn't change the resulting l.f.t. The upshot of this is that we can transform the problem of computing iterated l.f.t.s $g^k$ into the perhaps more familiar problem of taking powers $A^k$ of matrices.

More explicitly, in your example case, we can take any preimage of $\frac{1}{x + 1}$ under the homomorphism, say, $$A := \begin{pmatrix}0 & 1 \\ 1 & 1\end{pmatrix},$$ and compute its powers (and apply the homomorphism to produce the resulting l.f.t.). Since you already have a candidate answer for the general formula, you can simply prove it by induction. On the other hand, if you didn't know ahead of time what the answer ought to be, you could compute the general power $A^k$ by writing it in terms of its in Jordan normal form, $A = PJP^{-1}$, and compute $A^k = P J^k P^{-1}$. The eigenvalues of $A$ are the roots of $$\lambda(\lambda - 1) - 1 = \lambda^2 - \lambda - 1,$$ namely the Golden Ratio $\phi$ and its conjugate. But the familiar explicit formula for the $k$th term of the Fibonacci sequence is given exactly as a sum of powers of these two roots, which explains the appearance of that sequence here.

The same technique works for general $g$ too, which the minor complication that if the preimage matrices of $g$ are defective, then the formula for the $n$th power assumes a slightly different form, i.e., it is no longer (up to similarity) just a sum of powers of the eigenvalues.

(Strictly speaking, we should think of l.f.t.s not as maps from $\mathbb{R}$ to itself, but rather as maps from the projective line $\mathbb{P}^1$ to itself, in which setting they're defined everywhere. In particular, this means for a particular $g$ that $f\left(-\frac{d}{c}\right) = \infty$ and $f(\infty) = \frac{a}{c}$.)

Answer 3

The following is a modified excerpt from one of my blog posts:

BEGIN EXCERPT

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$, we have $$f(x)=(g\circ h\circ g^{-1})(x)$$ and so $$f^{\circ n}(x)=(g\circ h^{\circ n}\circ g^{-1})(x)$$ $$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}}$$

END EXCERPT

If any of this is confusing to you, I encourage you to go read the whole blog post.