+- Tetration Forum (https://tetrationforum.org)
+-- Forum: Tetration and Related Topics (https://tetrationforum.org/forumdisplay.php?fid=1)
+--- Forum: Mathematical and General Discussion (https://tetrationforum.org/forumdisplay.php?fid=3)
+--- Thread: Fibonacci as iteration of fractional linear function (/showthread.php?tid=1607)
Fibonacci as iteration of fractional linear function - bo198214 - 08/04/2022
I found an interesting expression of the fibonacci sequence as iteration of the function
\[f(z) = \frac{1}{1+z}\]
if we look at it:
\begin{align}
f^{\circ 2}(z) &= \frac{1}{1+\frac{1}{z+1}} = \frac{1+z}{2+z}\\
f^{\circ 3}(z) &= \frac{1}{1+\frac{1+z}{2+z}} = \frac{2+z}{3+2z}\\
f^{\circ 4}{z} &= \frac{1}{1+\frac{2+z}{3+2z}} = \frac{3+2z}{5+3z}\\
\end{align}
So we see already the scheme
\[ f^{\circ n}(z) = \frac{\phi_n + \phi_{n-1}z}{\phi_{n+1} + \phi_n z}\]
where \(\phi_n\) is the Fibonacci sequence.
There is a well known continuous formula for the fibonacci sequence:
\[\phi_t = \frac{\Phi^t - \Psi^t}{\Phi -\Psi}, \Phi,\Psi=\frac{1\pm \sqrt{5}}{2}\]
which we can use in our iteration formula.
The linear fraction \(f\) has the fixed points \(\Phi\) and \(\Psi\) (solution of \(1=z+z^2\)).
Unfortunately it is not a nice continuous iteration, because for non-integer t we have an imaginary part (due to \(\Psi\) being negative). This has to do with the pole in the middle between the two fixed points which would not allow for e.g. a real half iterate.
Nonetheless we can look at the complex behaviour (here we look at the function \(f^{\circ t}(z) - z\) to better see the fixed points but still see the poles):
We see how the pole of the iterate moves from one fixed point to the other in an S-spiral (I love S-spirals! lol).
The t-iterates are analytic for each t at both fixed points.
Hence we talk about *regular* iteration. The continuous version of the Fibonacci sequence can be obtained / is regular iteration.
And again we have the case that we can continue the regular iteration from one fixed point to the other (though not through the pole but beside the pole) which is not the case for e.g. the regular iteration of \(b^z\) and probably most other functions (and for which JmsNxn is still owing a proof
). And again JmsNxn would say that we don't have a vicinity around both fixed points where each iterate is holomorphic 
RE: Fibonacci as iteration of fractional linear function - Gottfried - 08/04/2022
(08/04/2022, 10:48 AM)bo198214 Wrote: I found an interesting expression of the fibonacci sequence as iteration of the function
\[f(z) = \frac{1}{1+z}\]
Just to compare an exercise in iteration of mine, perhaps there is some more interesting stuff inside (Otoh I didn't arrive at a two-fixpoint analysis). It's an old material, for instance I express it in terms of "bell"-matrix (or "matrix-operator") for which I later used "carleman" matrix. Also perhaps a simple exposition of the matrix-diagonalization-concept for the fractional iteration and Schroeder-concept.
RE: Fibonacci as iteration of fractional linear function - JmsNxn - 08/04/2022
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?
RE: Fibonacci as iteration of fractional linear function - Gottfried - 08/04/2022
(08/04/2022, 10:48 AM)bo198214 Wrote: Unfortunately it is not a nice continuous iteration, because for non-integer t we have an imaginary part (due to \(\Psi\) being negative). This has to do with the pole in the middle between the two fixed points which would not allow for e.g. a real half iterate.
Would it be good to have a "dual"-to-f(x)-function which is real on the real argument, and where \( f_d^{o2k}(x)=f^{o2k}(x) \) but \( f_d^{o1+2k}(x) \ne f^{o1+2k}(x) \) ?
Perhaps \( f_d(x) \) is better suited for your discussion?
See the pink line for \( f^h(x) \) and the blue line for \( f_d^h(x) \) starting at \(x=1\) for \( h=0..4 \)
RE: Fibonacci as iteration of fractional linear function - bo198214 - 08/04/2022
(08/04/2022, 05:43 PM)JmsNxn Wrote: 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\).
RE: Fibonacci as iteration of fractional linear function - bo198214 - 08/04/2022
(08/04/2022, 08:51 PM)Gottfried Wrote: Would it be good to have a "dual"-to-f(x)-function which is real on the real argument, and where \( f_d^{o2k}(x)=f^{o2k}(x) \) but \( f_d^{o1+2k}(x) \ne f^{o1+2k}(x) \) ?
Perhaps \( f_d(x) \) is better suited for your discussion?
From the standpoint of regular iteration there is only the one (on fractional linear functions), and messing with it is blasphemy
RE: Fibonacci as iteration of fractional linear function - JmsNxn - 08/04/2022
Is there a way to perform, let's say, "a crescent iteration" on the fibonacci sequence, so that we somehow map it to the reals?
We can always multiply by a 1-periodic function \(\theta(z)\), would it be possible to make \(\theta(z)F(z)\) real valued?
I've always wondered that, but I could never think of a solution; now seems as good a time to ask as any.
RE: Fibonacci as iteration of fractional linear function - Daniel - 08/04/2022
(08/04/2022, 09:40 PM)JmsNxn Wrote: Is there a way to perform, let's say, "a crescent iteration" on the fibonacci sequence, so that we somehow map it to the reals?
We can always multiply by a 1-periodic function \(\theta(z)\), would it be possible to make \(\theta(z)F(z)\) real valued?
I've always wondered that, but I could never think of a solution; now seems as good a time to ask as any.
See Fibonacci almost to the bottom of the page for a real iteration of the Fibonacci series.
RE: Fibonacci as iteration of fractional linear function - JmsNxn - 08/04/2022
(08/04/2022, 10:38 PM)Daniel Wrote:(08/04/2022, 09:40 PM)JmsNxn Wrote: Is there a way to perform, let's say, "a crescent iteration" on the fibonacci sequence, so that we somehow map it to the reals?
We can always multiply by a 1-periodic function \(\theta(z)\), would it be possible to make \(\theta(z)F(z)\) real valued?
I've always wondered that, but I could never think of a solution; now seems as good a time to ask as any.
See Fibonacci almost to the bottom of the page for a real iteration of the Fibonacci series.
Could you elaborate, Daniel? Sorry, I'm not too sure what's going on here.
I understand you are writing:
\[
f(z) = \sum_{n=1}^\infty f_n \frac{z^n}{n!}\\
\]
Where now we are taking a parabolic iteration:
\[
f^{\circ t}(z)\\
\]
about \(0\), but how does this produce a fractional fibonacci that is real valued?
Not doubting you, just curious.
RE: Fibonacci as iteration of fractional linear function - bo198214 - 08/05/2022
(08/04/2022, 09:40 PM)JmsNxn Wrote: Is there a way to perform, let's say, "a crescent iteration" on the fibonacci sequence, so that we somehow map it to the reals?
We can always multiply by a 1-periodic function \(\theta(z)\), would it be possible to make \(\theta(z)F(z)\) real valued?
I've always wondered that, but I could never think of a solution; now seems as good a time to ask as any.
I thought Gottfried has the answer to that?