next up previous
Next: Example: finding a linear Up: Linear recursive sequences Previous: Example: solving a linear

Example: the formula for the Fibonacci sequence

As we worked out earlier, $ \{F_n\}$ satisfies a linear recurrence with characteristic polynomial $ x^2-x-1$. By the quadratic formula, this factors as $ (x-\alpha)(x-\beta)$ where $ \alpha=(1+\sqrt{5})/2$ is the golden ratio, and $ \beta=(1-\sqrt{5})/2$. The main theorem implies that there are constants $ A$ and $ B$ such that

$\displaystyle F_n = A \alpha^n + B \beta^n$

for all $ n$. Using $ F_0=0$ and $ F_1=1$ we obtain

$\displaystyle 0 = A + B, \qquad 1= A \alpha+B \beta.$

Solving for $ A$ and $ B$ yields $ A=1/(\alpha-\beta)$ and $ B=-1/(\alpha-\beta)$, so

$\displaystyle F_n = \frac{\alpha^n-\beta^n}{\alpha-\beta}
= \frac{1}{\sqrt{5}} ...
...t(\frac{1+\sqrt{5}}{2} \right)^n
- \left(\frac{1-\sqrt{5}}{2} \right)^n \right]$

for all $ n$.

Zvezdelina Stankova-Frenkel 2000-09-20