1
$\begingroup$

The Fibonacci sequence can be defined at $F_{n+1} = F_n + F_{n-1}$ for $n\ge0$ and with $F_0 = 0$ and $F_1 = 1$. It can be shown that the ratio between successive terms converges to

$$ \lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n} = \varphi = \frac{1+\sqrt{5}}{2}\approx 1.618$$

It seems harder to show exactly how quickly this convergence happens. Typically the rate of convergence would be computed as

$$ \lim_{n\rightarrow\infty} \frac{|\frac{F_{n+1}}{F_n}-\varphi|}{|\frac{F_n}{F_{n-1}}-\varphi|} = \mu$$

but this is hard to compute and for me has been going to either 0, 1, or $\varphi$ on paper. By computer the ratio of successive terms in the Fibonacci seqence shows a linear convergence, i.e., $\mu \in [0,1]$, of $1/\varphi^2 \approx .382$.

Can anyone show this analytically?

$\endgroup$
4
$\begingroup$

You get that $\frac{F_{n+1}}{F_n}$ alternates around $φ$ with $$ \frac{F_{n+1}}{F_n}-\frac{F_n}{F_{n-1}}=\frac{(-1)^{n-1}}{F_nF_{n-1}} $$ so that indeed the distance to $φ$ falls like $φ^{-2n}$.


If you want to be more exact, you know that $F_n=aφ^n+b(-φ)^{-n}$, $a\ne 0$, so that $$ \frac{F_{n+1}}{F_n}=φ\frac{a+b(-φ^2)^{-n-1}}{a+b(-φ^2)^{-n}} \implies \frac{F_{n+1}}{F_n}-φ=φ\frac{b(-φ^2)^{-n-1}(1-φ^2)}{a+b(-φ^2)^{-n}} $$ and thus the rate of linear convergence is $$ \frac{\frac{F_{n+1}}{F_n}-φ}{\frac{F_n}{F_{n-1}}-φ}=-φ^{-2}\frac{a+b(-φ^2)^{-n+1}}{a+b(-φ^2)^{-n}} $$ which converges to $-φ^{-2}$.

$\endgroup$
  • $\begingroup$ It looks like you are jumping to the limit of the absolute error for the sequence, instead of evaluating the limit I gave above? Also, I do not follow how you went from the left to the right side. $\endgroup$ – guitarphish Jul 6 at 16:58
  • $\begingroup$ Thank you for helping, by the way! The limit is the definition of the rate of convergence (en.wikipedia.org/wiki/Rate_of_convergence). If you are calculating the limit of the absolute error, which is what it looks like, that would be roughly the same thing (but it might not work for non-linear rates of convergence, not sure). So I am understanding the left side of your expression, but I am unable to find a path to the right side. $\endgroup$ – guitarphish Jul 6 at 17:09
  • $\begingroup$ In your "more exact" formula involving $a$ and $b$, you probably want $-1/\varphi$, which is $\frac{1-\sqrt5}2$, rather than $-\varphi$. $\endgroup$ – Andreas Blass Jul 6 at 17:15
  • $\begingroup$ @AndreasBlass : That's why the exponent is negative. As in $-1/φ=(-φ)^{-1}$. $\endgroup$ – LutzL Jul 6 at 17:38
  • $\begingroup$ I've worked it out to confirm that this works, the algebra is thick in this one but I ended up getting the anticipated result! Thank you again! $\endgroup$ – guitarphish Jul 6 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.