Problem 4.4

Fibonacci numbers

This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.22). We shall use the technique of generating functions to solve the Fibonacci recurrence. Define the generating function (or formal power series) $\mathcal{F}$ as

$$ \begin{aligned} \mathcal{F}(z) &= \sum_{i=0}^{\infty}F_iz^i \\ &= 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + 13z^7 + 21z^8 + \ldots, \end{aligned} $$

where $F_i$ is the $i$th Fibonacci number.

  1. Show that $\mathcal{F}(z) = z + z\mathcal{F}(z) + z^2\mathcal{F}$.
  2. Show that $$ \begin{aligned} \mathcal{F}(z) &= \frac{z}{1 - z - z^2} \\ &= \frac{z}{(1 - \phi z)(1 - \hat\phi z)} \\ &= \frac{1}{\sqrt5}\Big(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat{\phi} z}\Big) \end{aligned} $$ where $$ \phi = \frac{1 + \sqrt5}{2} = 1.61803\ldots \\ \hat\phi = \frac{1 - \sqrt5}{2} = -0.61803\ldots $$
  3. Show that $$ \mathcal{F}(z) = \sum_{i=0}^{\infty}\frac{1}{\sqrt5}(\phi^i - \hat{\phi}^i)z^i $$
  4. Use part (c) to prove that $F_i = \phi^i / \sqrt5$ for $i > 0$, rounded to the nearest integer. (Hint: Observe that $|\hat{\phi}| < 1$)

Part 1

$$ \begin{aligned} & z + z\mathcal{F}(z) + z^2\mathcal{F}(Z) = \\ & = z + z\sum_{i=0}^{\infty}F_iz^i + z^2\sum_{i=0}^{\infty}F_iz^i \\ & = z + \sum_{i=1}^{\infty}F_{i-1}z^i + \sum_{i=2}^{\infty}F_{i-2}z^i \\ & = z + F_1z + \sum_{i=2}^{\infty}(F_{i-1} + F_{i-2})z^i \\ & = z + F_1z + \sum_{i=2}^{\infty}F_iz^i \\ & = \mathcal{F}(z) \end{aligned} $$

Part 2

Let's just note that $\phi - \hat\phi = \sqrt5$, $\phi + \hat\phi = 1$ and $\phi\hat\phi = - 1$ (just calculate them):

$$ \begin{aligned} \mathcal{F}(z) &= \frac{\mathcal{F}(z)(1 - z - z^2)}{1 - z - z^2} \\ &= \frac{\mathcal{F}(z) - z\mathcal{F}(z) - z^2\mathcal{F}(z) - z + z}{1 - z - z^2} \\ &= \frac{\mathcal{F}(z) - \mathcal{F}(z) + z}{1 - z - z^2} \\ &= \frac{z}{1 - z - z^2} \\ &= \frac{z}{1 - (\phi + \hat\phi)z + \phi\hat\phi z^2} \\ &= \frac{z}{(1 - \phi z)(1 - \hat\phi z)} \\ &= \frac{\sqrt5 z}{\sqrt5 (1 - \phi z)(1 - \hat\phi z)} \\ &= \frac{(\phi - \hat\phi)z + 1 - 1}{\sqrt5 (1 - \phi z)(1 - \hat\phi z)} \\ &= \frac{(1 - \hat\phi z) - (1 - \phi z)}{\sqrt5 (1 - \phi z)(1 - \hat\phi z)} \\ &= \frac{1}{\sqrt5}\Big(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat\phi z}\Big) \\ \end{aligned} $$

Part 3

We have that:

$$ \frac{1}{1 - x} = \sum_{k=0}^{\infty}x^k \quad\text{when } |x| < 1 $$

Thus:

$$ \begin{aligned} \mathcal{F}(n) &= \frac{1}{\sqrt5}\Big(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat\phi z}\Big) \\ &= \frac{1}{\sqrt5}\Big(\sum_{i=0}^{\infty}\phi^i z^i - \sum_{i=0}^{\infty}\hat{\phi}^i z^i\Big) \\ &= \sum_{i=0}^{\infty}\frac{1}{\sqrt5}(\phi^i - \hat{\phi}^i) z^i \end{aligned} $$

Part 4

$$ \mathcal{F}(z) = \sum_{i=0}^{\infty}\alpha_iz^i \quad\text{ where } \alpha_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt5} $$

From this follows that $\alpha_i = F_i$, that is:

$$ F_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt5} = \frac{\phi^i}{\sqrt5} - \frac{\hat{\phi}^i}{\sqrt5} $$

For $i = 0$, $\phi/\sqrt5 = (\sqrt5 + 5)/10 > 0.5$. For $i > 2$, $|\hat{\phi}^i| < 0.5$.