Thread Rating:
  • 1 Vote(s) - 5 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Fibonacci as iteration of fractional linear function
#1
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 Wink ). And again JmsNxn would say that we don't have a vicinity around both fixed points where each iterate is holomorphic Big Grin
Reply
#2
(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.
Gottfried Helms, Kassel
Reply
#3
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?
Reply
#4
(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 \)

   
Gottfried Helms, Kassel
Reply
#5
(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\).
Reply
#6
(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 Big Grin
Reply
#7
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.
Reply
#8
(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.
Daniel
Reply
#9
(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.
Reply
#10
(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?
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Constructing a real valued Fibonacci iteration--its relation to \(1/1+z\) JmsNxn 7 272 08/13/2022, 12:05 AM
Last Post: JmsNxn
  The iterational paradise of fractional linear functions bo198214 7 259 08/07/2022, 04:41 PM
Last Post: bo198214
  Describing the beta method using fractional linear transformations JmsNxn 5 244 08/07/2022, 12:15 PM
Last Post: JmsNxn
  Apropos "fix"point: are the fractional iterations from there "fix" as well? Gottfried 12 797 07/19/2022, 03:18 AM
Last Post: JmsNxn
  Constructing an analytic repelling Abel function JmsNxn 0 199 07/11/2022, 10:30 PM
Last Post: JmsNxn
  A related discussion on interpolation: factorial and gamma-function Gottfried 9 18,159 07/10/2022, 06:23 AM
Last Post: Gottfried
  A random question for mathematicians regarding i and the Fibonacci sequence. robo37 1 4,045 06/27/2022, 12:06 AM
Last Post: Catullus
  Fractional iteration of x^2+1 at infinity and fractional iteration of exp bo198214 17 29,684 06/11/2022, 12:24 PM
Last Post: tommy1729
  A Holomorphic Function Asymptotic to Tetration JmsNxn 2 1,906 03/24/2021, 09:58 PM
Last Post: JmsNxn
  [exercise] fractional iteration of f(z)= 2*sinh (log(z)) ? Gottfried 4 2,914 03/14/2021, 05:32 PM
Last Post: tommy1729



Users browsing this thread: 1 Guest(s)