# Fibonacci Sequence: Rate of Convergence

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?

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}$$.
• In your "more exact" formula involving $a$ and $b$, you probably want $-1/\varphi$, which is $\frac{1-\sqrt5}2$, rather than $-\varphi$. – Andreas Blass Jul 6 at 17:15
• @AndreasBlass : That's why the exponent is negative. As in $-1/φ=(-φ)^{-1}$. – LutzL Jul 6 at 17:38