TITLE: Why is $F_{i+2} ≥ (\frac {1+\sqrt5} {2})^i$ in the Fibonacci series?
QUESTION [2 upvotes]: 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?

REPLY [0 votes]: 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'}$
{"set_name": "stack_exchange", "score": 2, "question_id": 2093661}