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

Question

$$\varphi = \frac{1 + \sqrt{5}}{2}$$

We want to prove that ratio of two consecutive Fibonacci numbers approaches $\varphi$ by induction and also utilizing Newton-Raphson method for approximating $\sqrt{5}$ as a rational number with relatively prime numerators and denominators.

Let us first define the Fibonacci Sequence and then write down what we want to prove using the symbolic notation.

$$\phi_1,\phi_2 = 1$$ $$\phi_{n+2} = \phi_{n+1} + \phi_{n}$$ $$1 \le n$$

$$n \to \infty \Rightarrow \frac{\phi_{n+1}}{\phi_{n}} \to \varphi$$

First we need rational approximations for the irrational number $\sqrt{5}$, so we can connect it up to integers:

$$x_{n} = \frac{a_{n}}{b_{n}}$$

$$x_{1} = \frac{2}{1} = \frac{a_1}{b_1}$$

Where the limit as $n$ goes to infinity is $\sqrt{5}$. So according to the Newton-Raphson method we can write that,

$$x_{n+1} = x_n - \frac{F(x_n)}{F'(x_n)} = \frac{x_n^2 + 5}{2x_n}$$

Substituting the $\frac{a_n}{b_n}$ and $\frac{a_{n+1}}{b_{n+1}}$ respectively to the places of $x_n$ and $x_{n+1}$ we will get the following rational number with integer numerator and denominator,

$$\frac{a_{n+1}}{b_{n+1}} = \frac{a_n^2 + 5b_n^2}{2a_nb_n}$$

So that

$$a_{n+1} = a_n^2 + 5b_n^2$$ $$b_{n+1} = 2a_nb_n$$

Let us define

$$\varphi_n = \frac{1 + \frac{a_n}{b_n}}{2} = \frac{a_n + b_n}{2b_n}$$

$$n \to \infty \Rightarrow \varphi_{n} \to \varphi$$

For $n = 1$ (the first case):

$$\varphi_1 = \frac{1 + \frac{2}{1}}{2} = \frac{3}{2}$$

Numerator and denominator are two consecutive Fibonacci numbers, respectively the $\phi_4$ and $\phi_3$. Now here goes our induction hypothesis for $1 \le n$:

if numerator and denominator of $\varphi_n$ are two consecutive Fibonacci numbers, respectively $\phi_{3\cdot2^{n - 1} + 1}$ and $\phi_{3\cdot2^{n - 1}}$ (as the $\phi_{4}$ and $\phi_{3}$ are), then the numerator and denominator of $\varphi_{n+1}$ will be again two consecutive Fibonacci numbers, respectively $\phi_{3\cdot2^{n} + 1}$ and $\phi_{3\cdot2^{n}}$.

$$\varphi_1 = \frac{3}{2} = \frac{\phi_4}{\phi_3} = \frac{\phi_{3\cdot2^{0} + 1}}{\phi_{3\cdot2^{0}}}$$ $$\varphi_2 = \frac{13}{8} = \frac{\phi_7}{\phi_6} = \frac{\phi_{3\cdot2^{1} + 1}}{\phi_{3\cdot2^{1}}}$$ $$\varphi_3 = \frac{233}{144} = \frac{\phi_{13}}{\phi_{12}} = \frac{\phi_{3\cdot2^{2} + 1}}{\phi_{3\cdot2^{2}}}$$ $$...$$ If we can prove that, we will be proved that ratio of two consecutive Fibonacci numbers approaches $\varphi$, of course if i have no mistake to here.

Here is our assumption:

$$\varphi_n = \frac{a_n + b_n}{2b_n} = \frac{\phi_{3\cdot2^{n - 1} + 1}}{\phi_{3\cdot2^{n - 1}}}$$

And here is what we want to prove (i rewritten and manipulated the statement using previous definitions of $a_{n+1}$ and $b_{n+1}$):

$$\varphi_{n+1} = \frac{(a_n + b_n)^2 + (2b_n)^2 }{(2b_n)^2} = \frac{\phi_{3\cdot2^{n} + 1}}{\phi_{3\cdot2^{n}}}$$

$$\varphi_{n+1} = \varphi_{n}^2 + 1 = \frac{\phi_{3\cdot2^{n} + 1}}{\phi_{3\cdot2^{n}}}$$

It gets really cumbersome for me after this point. Anyone could please give me hints or point out my mistakes if there is?

Answer 1

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.

Answer 2

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.