Why is $F_{i+2} ≥ (\frac {1+\sqrt5} {2})^i$ in the Fibonacci series?

Question

In our algorithms class we defined the Fibonacci series:

$$F_0 = 0$$ $$F_1 = 1$$ $$F_{i+2} = F_i + F_{i+1}$$

After that we used that $F_{i+2} ≥ (\frac {1+\sqrt5} {2})^i$ but I can't see why that is true. Since it's the Fibonacci series I suspect that there should be a common known proof. If there isn't, how could you prove it?

Answer 1

Prove it inductively, noting that $$ \left( \frac{1+\sqrt 5}{2}\right)^{i+2} = \left( \frac{1+\sqrt 5}{2}\right)^{i+1} + \left( \frac{1+\sqrt 5}{2}\right)^{i} $$

Answer 2

Not a prove as to why $F_{n+2} > (\frac {1+\sqrt 5}{2})^n$ But some insight why that expression is relevant.

Suppose, $\frac {F_{n+1}}{F_n}$ is converging to something.

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

So, supposing that this ratio is indeed converging. (which I have not proven, and leave as an exercise to the reader), then lets say it is coverging to some value x.

If $\frac {F_{n+1}}{F_n} = x,$ then $\frac {F_{n-1}}{F_n} = \frac 1x$

$x = 1 + \frac 1x\\ x^2 - x - 1=0$

$\frac {1+\sqrt 5}{2}$ is the only positive root of that polynomial.

Here is another idea.

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

$\begin{bmatrix} F_{n+1}\\F_{n}\end{bmatrix} = \begin{bmatrix} 1&1\\1&0\end{bmatrix}^n\begin{bmatrix} 1\\0\end{bmatrix}$

The characteristic equation of $\begin{bmatrix} 1&1\\1&0\end{bmatrix}$ is $\lambda^2 - \lambda -1$ (coincidence? no.)

I am going to call the roots $\phi = \frac {1+\sqrt 5}{2}, \phi' = \frac {1-\sqrt 5}{2}$

$\begin{bmatrix} F_{n+1}\\F_{n}\end{bmatrix} = \frac 1{\phi - \phi'}\begin{bmatrix} \phi&\phi'\\1&1\end{bmatrix}\begin{bmatrix} \phi^n&0\\0&\phi'^n\end{bmatrix}\begin{bmatrix} 1&-\phi'\\-1&\phi\end{bmatrix}\begin{bmatrix} 1\\0\end{bmatrix}$

$F_n = \frac {\phi^n - \phi'^n}{\phi-\phi'}$