4-4 Fibonacci numbers

This problem develops properties of the Fibonacci numbers, which are defined by recurrence $\text{(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 + \cdots, \end{aligned}$$

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

a. Show that $\mathcal F(z) = z + z\mathcal F(z) + z^2\mathcal F$.

b. Show that

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

where

$\phi = \frac{1 + \sqrt 5}{2} = 1.61803\ldots$

and

$\hat\phi = \frac{1 - \sqrt 5}{2} = -0.61803\ldots$

c. Show that

$$\mathcal F(z) = \sum_{i = 0}^{\infty}\frac{1}{\sqrt 5}(\phi^i - \hat{\phi}^i)z^i.$$

d. Use part (c) to prove that $F_i = \phi^i / \sqrt 5$ for $i > 0$, rounded to the nearest integer. ($\textit{Hint:}$ Observe that $|\hat{\phi}| < 1$.)

a.

$$\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_i z^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}$$

b. Note that $\phi - \hat\phi = \sqrt 5$, $\phi + \hat\phi = 1$ and $\phi\hat\phi = - 1$.

$$\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{\sqrt 5 z}{\sqrt 5 (1 - \phi z)(1 - \hat\phi z)} \\ & = \frac{(\phi - \hat\phi)z + 1 - 1}{\sqrt 5 (1 - \phi z)(1 - \hat\phi z)} \\ & = \frac{(1 - \hat\phi z) - (1 - \phi z)}{\sqrt 5 (1 - \phi z)(1 - \hat\phi z)} \\ & = \frac{1}{\sqrt 5}\Big(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat\phi z}\Big). \end{aligned}$$

c. We have $\frac{1}{1 - x} = \sum_{k = 0}^{\infty}x^k$, when $|x| < 1$, thus

$$\begin{aligned} \mathcal F(n) & = \frac{1}{\sqrt 5}\Big(\frac{1}{1 - \phi z} - \frac{1}{1 - \hat\phi z}\Big) \\ & = \frac{1}{\sqrt 5}\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}{\sqrt 5}(\phi^i - \hat{\phi}^i) z^i. \end{aligned}$$

d. $\mathcal F(z) = \sum_{i = 0}^{\infty}\alpha_i z^i$ where $\alpha_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt 5}$. From this follows that $\alpha_i = F_i$, that is

$$F_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt 5} = \frac{\phi^i}{\sqrt 5} - \frac{\hat{\phi}^i}{\sqrt 5},$$

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