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

$$\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?

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.

• I couldn't think it can be simple as that :D Thanks for the proof. It is a very brilliant one. Jun 5 '19 at 18:58
• This may interest you as well: math.stackexchange.com/questions/728973/… Jun 5 '19 at 19:13
• Aynen boyle iste Ibocan, bazen öyle prooflar vardır ki sasirtir insani.
– TBTD
Jun 5 '19 at 19:30

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.