next up previous contents
Next: Second Method Up: Generating Functions Previous: Generating Functions   Contents

First method

Try a solution of the form $ F_n = \alpha^n$. Then we get $ \alpha^2 - \alpha - 1 = 0$ and $ \alpha = \frac{1 \pm \sqrt{5}}{2}$. We then take

$\displaystyle F_n = A \left( \frac{1 + \sqrt{5}}{2} \right)^n +
B \left( \frac{1 - \sqrt{5}}{2} \right)^n
$

and use the initial conditions to determine $ A$ and $ B$. It turns out that

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

Note that $ \frac{1 + \sqrt{5}}{2} > 1$ and $ \lvert\frac{1 - \sqrt{5}}{2}\rvert < 1$ so the solution grows exponentially. A shorter form is that $ F_n$ is the nearest integer to $ \frac{1}{\sqrt{5}}
\left( \frac{1 + \sqrt{5}}{2} \right)^n$.

root 2002-06-10