Worked exercise — Binet's formula for Fibonacci

Problem

Fibonacci sequence: $F_{n+1} = F_n + F_{n-1}$ with $F_0 = 0$, $F_1 = 1$. Show (by induction or directly) that $F_n = \frac{\varphi^n - \psi^n}{\sqrt5}, \qquad \varphi = \frac{1+\sqrt5}{2},\quad \psi = \frac{1-\sqrt5}{2}$ (Binet’s formula). Compute also $\displaystyle\lim_{n\to+\infty}\frac{F_{n+1}}{F_n}$.

Solution

Binet’s formula. $\varphi$ and $\psi$ are the roots of the characteristic equation $x^2 = x + 1$, that is $x^2 - x - 1 = 0$. Every sequence of the form $x^n$ with $x$ a root satisfies the recurrence $F_{n+1} = F_n + F_{n-1}$; by linearity so does $F_n = A\varphi^n + B\psi^n$. Imposing the initial conditions: $F_0 = A + B = 0,\qquad F_1 = A\varphi + B\psi = 1.$ From $B = -A$ it follows that $A(\varphi-\psi) = 1$; since $\varphi - \psi = \sqrt5$, we have $A = 1/\sqrt5$, $B = -1/\sqrt5$, whence $F_n = \frac{\varphi^n - \psi^n}{\sqrt5}.$ Limit of the ratio. Since $|\psi| = \left|\frac{1-\sqrt5}{2}\right| \approx 0{,}618 < 1$, the term $\psi^n \to 0$ and $\varphi^n$ dominates. Hence $\frac{F_{n+1}}{F_n} = \frac{\varphi^{n+1} - \psi^{n+1}}{\varphi^n - \psi^n} \to \varphi = \boxed{\frac{1+\sqrt5}{2}}\approx 1{,}618,$ the golden ratio.

Links

Topics: Sequences
Concepts: Limit of a sequence · Recursively defined sequence
Skills: Computing limits · Proving
People: Binet · Leonardo Fibonacci
Exercise type: Computing a limit · Proof