Fibonacci as iteration of fractional linear function

[bo198214]

Woah that's super cool!

Do you think it would be possible to do this for other linear recurrence relations?

For instance, if:

\[
\psi_n = \sum_{k=0}^m a_k r_k^n\\
\]

Could we find a similar relationship to some other fractional linear transformation?

For \(m=2\), yes! This whole thing works with linear fractional functions because they are representable as 2x2 matrices.
Typically one takes for \( \frac{az+b}{cz+d} \) the matrix \( \left(\begin{array}{rr}a & c\\b & d\end{array}\right)\).
One can show that multiplication of matrices corresponds to composition of the linear fractional functions.
E.g. the fibonacci sequence can be expressed as:
\[\left(\begin{array}{r}f_{n}\\f_{n+1}\end{array}\right) =  \left(\begin{array}{rr}0 & 1\\1 & 1\end{array}\right)\left(\begin{array}{r}f_{n-1}\\f_{n}\end{array}\right)\]
And voilá you have already \(\frac{1}{z+1}\).

So you do a regular iteration on that function and you have continuous version of your recurrence.
However to get an explicit formula (which you typically would not get when messing with Schröder series') you can use diagonalization of the matrix.
I.e. \(M = A D A^{-1}\) and then you know that D^t is just each coefficient on the diagonal taken to the power of t. And so you have an explicit formula 
\( M^t = A D^t A^{-1}\).

But you don't need to rely on linear fractional functions though, you can just take the recurrence matrix (also bigger than 2x2) and do the diagonalization stuff. I just don't know whether this could represent regular iteration of some corresponding functions ...

Actually the Schröder iteration can be based on a similar mechanism (see Gottfried's article), you work with the Carleman-Matrix (which is not 2x2 but infinite though) which represents the function developed at the fixed point and multiplication of those matrices correspond to composition of the functions.
Then with diagonalization one can get the formula for \(M^t\).