Proving that ratio of two consecutive Fibonacci numbers to converges to golden ratio by induction

This is just a suggestion:

From $F_{n+1}=F_n+F_{n-1}$, define the ratio as

$r_{n+1}=\frac{F_{n+1}}{F_n}=1+\frac{F_{n-1}}{F_n}=1+\frac{1}{r_n}$

There are a few thing too do now, for instance to show that $r_n$ converges. Once that is done, the limit should satisfy $$x=1+\frac{1}{x}$$ which has the golden mean as solution.

Also notice that $$ \begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix} $$ And iterating n times you get $$ \begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F_1\\ F_0 \end{bmatrix} $$

Using the diagonal decomposition of the matrix involve you get again something related to the golden mean.


With $\phi_n:=\dfrac{F_{n+1}}{F_n}$,

$$F_{n+2}=F_{n+1}+F_n\iff \phi_{n+1}=1+\frac1{\phi_{n}}.$$

Then if the sequence of $\phi_n$ converges, it converges to a root of

$$p=1+\frac1p.$$

As all terms are positive, convergence must be to the positive root.


As one can observe, the $\phi_n$ are alternating around $\phi$ and getting closer and closer. We can show that

$$|\phi_{n+1}-\phi|<|\phi_n-\phi|.$$

Indeed

$$|\phi_{n+1}-\phi|=\left|1+\frac1{\phi_{n}}-\phi\right|=\left|\frac1{\phi_{n}}-\frac1\phi\right|=\frac{|\phi_n-\phi|}{\phi_{n}\phi}<|\phi_n-\phi|.$$

As $\phi_n>1$, then the distance to $\phi$ is at least divided by $\phi$ (in fact by nearly $\phi^2$) on every iteration, and linear convergence is guaranteed.