This problem develops properties of the Fibonacci numbers, which are defined by the 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{split} \mathcal{F}(z) &= \sum\limits_{i=0}^{\infty} \mathcal{F}_i z^i\\ &= 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + 13z^7 + 21z^8 + \cdots ,\\ \end{split}\]

where \(\mathcal{F}_i\) is the \(i\)th Fibonacci number.

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

Note that \(\mathcal{f}_i = \mathcal{F}_{i-1} + \mathcal{F}_{i-2} \forall i \geq 2\), \(\mathcal{F}_{0} = 0\) and \(\mathcal{F}_{1} = 1\).

\[\begin{split} z + z\mathcal{F}(z) + z^2 \mathcal{F}(z) &= z + z \sum\limits_{i=0}^{\infty} \mathcal{F}_i z^i + z^2 \sum\limits_{i=0}^{\infty} \mathcal{F}_i z^i \\ &= z + \sum\limits_{i=1}^{\infty} \mathcal{F}_{i-1} z^i + \sum\limits_{i=0}^{\infty} \mathcal{F}_{i-2} z^i \\ &= z + \mathcal{F}_1 z + \sum\limits_{i=2}^{\infty} (\mathcal{F}_{i-1} + \mathcal{F}_{i-2})z^i \\ &= z + \mathcal{F}_1 z + \sum\limits_{i=2}^{\infty} (\mathcal{F}_{i})z^i \\ &= \sum\limits_{i=0}^{\infty} \mathcal{F}_i z^i \\ &= \mathcal{F}(z) \\ \end{split}\]

b. Show that

\[\begin{split} \mathcal{F}(z) &= \frac{z}{1-z-z^2} \\ &= \frac{z}{(1 - \phi z)(1 - \hat{\phi} z)} \\ &= \frac{1}{\sqrt{5}} \left( \frac{1}{1-\phi z} - \frac{1}{1-\hat{\phi} z} \right), \end{split}\]

where

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

and

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

\[\begin{split} \mathcal{F}(z) &= \mathcal{F}(z) \left(\frac{1-z-z^2}{1-z-z^2}\right) \\ &= \frac{\mathcal{F}(z) - z \mathcal{F}(z) - z^2 \mathcal{F}(z)}{1 - z - z^2} \end{split}\]

Let’s borrow from question a. in order to simplify this expression.

\[\begin{split} &= \frac{\mathcal{F}(z) - (z + z \mathcal{F}(z) + z^2 \mathcal{F}(z)) + z}{1 - z - z^2} \\ &= \frac{\mathcal{F}(z) - \mathcal{F}(z) + z}{1 - z - z^2} \\ &= \frac{z}{1 - z - z^2} \\ \end{split}\]

So far so good. The following identities are helpful in continuing with this problem. \(\phi + \hat{\phi} = \frac{1 + \sqrt{5} + 1 - \sqrt{5}}{2} = 1\), \(\phi \hat{\phi} = \frac{1 - \sqrt{5} + \sqrt{5} - 5}{2} = -1\) and \(\phi - \hat{\phi} = \frac{1 + \sqrt{5} - 1 + \sqrt{5}}{2} = \sqrt{5}\).

\[\begin{split} &= \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}} \left( \frac{1 - \hat{\phi} z}{(1 - \phi z)(1 - \hat{\phi}z)} - \frac{1 - \phi z}{(1 - \phi z)(1 - \hat{\phi}z)} \right) \\ &= \frac{1}{\sqrt{5}} \left( \frac{1}{1 - \phi z} - \frac{1}{1 - \hat{\phi}z} \right) \\ \end{split}\]

c. Show that

\[\mathcal{F}(z) = \sum\limits_{i=0}^{\infty} \frac{1}{\sqrt{5}}(\phi ^i - \hat{\phi^i})z^i\]

For \(\left\lvert x \right\rvert > 1\) we have \(\frac{1}{1-x} = \sum\limits_{k=0}^{\infty} x ^k\).

\[\begin{split} \mathcal{F}(z) &= \frac{1}{\sqrt{5}}\left( \frac{1}{1 - \phi z} - \frac{1}{1 - \hat{\phi} z} \right) \\ &= \frac{1}{\sqrt{5}} \left( \sum\limits_{i=0}^{\infty} (\phi z) ^ i - \sum\limits_{i=0}^{\infty} (\hat{\phi} z)^i \right) \\ &= \frac{1}{\sqrt{5}} \left( \sum\limits_{i=0}^{\infty} \phi ^i z ^ i - \sum\limits_{i=0}^{\infty} \hat{\phi^i} z^i \right) \\ &= \sum\limits_{i=0}^{\infty} \frac{1}{\sqrt{5}}(\phi ^i z ^ i - \hat{\phi^i} z^i)\\ &= \sum\limits_{i=0}^{\infty} \frac{1}{\sqrt{5}}(\phi ^i - \hat{\phi^i})z^i \\ \end{split}\]

d. Use part c to prove that \(F_i = \frac{\phi^i}{\sqrt{5}}\) for \(i > 0\), rounded to the nearest integer. (Hint: Observe that \(\left\lvert \hat{\phi} \right\rvert\) < 1.)

By this problem’s definition and part c, \(F_i = \frac{1}{\sqrt{5}}(\phi ^i - \hat{\phi^i}) = \frac{\phi ^ i}{\sqrt{5}} - \frac{\hat{\phi}^i}{\sqrt{5}}\). For all values of \(i\), the subtracted term \(\frac{\hat{\phi}^i}{\sqrt{5}}\) is less than \(0.5\) which is therefore effectively rounding the value determined by \(\frac{\phi ^ i}{\sqrt{5}}\). Thus this problem’s popular claim (see SICP 1.13) is simply a restatement of the conclusions of part c.