mathschallenge.net

Problem

The Fibonacci sequence is defined by the second order recurrence relation $F_{n+2} = F_{n+1} + F_n$, where $F_1 = 1$ and $F_2 = 1$.

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...$

Assuming that ratio of adjacent terms in the Fibonacci sequence $\dfrac{F_{n+1}}{F_n}$ tends to a limit, $\phi$, as $n$ increases, prove that $\phi = \dfrac{\sqrt{5} + 1}{2}$.

Solution

If the limit exists for $n \ge L$, it follows that $\phi = \dfrac{F_{L+1}}{F_L} = \dfrac{F_{L+2}}{F_{L+1}}$.

But $\dfrac{F_{L+2}}{F_{L+1}} = \dfrac{F_{L+1} + F_L}{F_{L+1}} = 1 + \dfrac{F_L}{F_{L+1}}$.

Therefore $\phi = 1 + 1/\phi$, and multiplying through by $\phi$, we get the quadratic equation $\phi^2 = \phi + 1$ or $\phi^2 - \phi - 1 = 0$.

Solving this quadratic, and ignoring the negative root as the ratio of adjacent terms will be positive, we get $\phi = \dfrac{\sqrt{5} + 1}{2}$.   Q. E. D.

Using the following identity prove that the limit exists and $\phi = \dfrac{\sqrt{5} + 1}{2}$.

(See Fibonacci Sequence for proof of identity.)