Fibonacci Sequence: Rate of Convergence

Question

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?

Answer 1

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}$.