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}\) for the Fibonacci sequence as
\[\begin{align*} \mathcal{F}(z) &= \sum_{i=0}^{\infty} F_i z^i \\ &= 0 + z + z^2 + 2z^3 + 3z^4 + 5z^5 + 8z^6 + 13z^7 + 21z^8 + \cdots\end{align*}\]where \(F_i\) is the \(i\)th Fibonacci number.
Show that \(\mathcal{F}(z) = z + z\mathcal{F}(z) + z^2\mathcal{F}(z)\).
Show that
\[\begin{align*}\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{align*}\]where \(\phi = \frac{1+\sqrt{5}}{2} = 1.61803\ldots\) and \(\hat{\phi} = \frac{1-\sqrt{5}}{2} = -0.61803\ldots\).
Show that \(\mathcal{F}(z) = \sum_{i=0}^{\infty} \frac{1}{\sqrt{5}}(\phi^i - \hat{\phi}^i)z^i\).
Use part (c) to prove that \(F_i = \phi^i/\sqrt{5}\) for \(i > 0\), rounded to the nearest integer. (Hint: Observe that \(\vert\hat{\phi}\vert < 1\).)
A generating function is like packaging an entire sequence into a single mathematical object. Instead of working with the sequence \(F_0, F_1, F_2, \ldots\) directly, we encode it as coefficients of powers of \(z\). The beauty of this approach is that algebraic manipulations on the generating function translate into statements about the sequence. By manipulating \(\mathcal{F}(z)\) using algebra, we can extract a closed-form formula for \(F_i\) without solving the recurrence directly.
A
The goal here is to translate the Fibonacci recurrence (\(F_i = F_{i-1} + F_{i-2}\)) into an equation about the generating function. We start by writing out \(\mathcal{F}(z)\) and then manipulate it using the recurrence relation.
Using the Fibonacci recurrence \(F_i = F_{i-1} + F_{i-2}\):
\[\begin{align*} \mathcal{F}(z) &= \sum_{i=0}^{\infty} F_i z^i\\ &= F_0 + F_1 z + \sum_{i=2}^{\infty} F_i z^i\\ &= 0 + z + \sum_{i=2}^{\infty} (F_{i-1} + F_{i-2}) z^i\\ &= z + \sum_{i=2}^{\infty} F_{i-1} z^i + \sum_{i=2}^{\infty} F_{i-2} z^i\\ &= z + z\sum_{i=2}^{\infty} F_{i-1} z^{i-1} + z^2\sum_{i=2}^{\infty} F_{i-2} z^{i-2}\\ &= z + z\sum_{j=1}^{\infty} F_j z^j + z^2\sum_{k=0}^{\infty} F_k z^k\\ &= z + z(\mathcal{F}(z) - F_0) + z^2\mathcal{F}(z)\\ &= z + z\mathcal{F}(z) + z^2\mathcal{F}(z) \end{align*}\]B
From part A: \(\mathcal{F}(z) = z + z\mathcal{F}(z) + z^2\mathcal{F}(z)\)
Solving for \(\mathcal{F}(z)\):
\[\mathcal{F}(z)(1 - z - z^2) = z\] \[\mathcal{F}(z) = \frac{z}{1-z-z^2}\]The golden ratio \(\phi = \frac{1+\sqrt{5}}{2}\) and \(\hat{\phi} = \frac{1-\sqrt{5}}{2}\) are roots of \(x^2 = x + 1\), or equivalently \(x^2 - x - 1 = 0\).
Factoring \(1 - z - z^2 = -(z^2 + z - 1)\), and noting that if \(x^2 - x - 1 = 0\), then \((1/x)^2 + (1/x) - 1 = 0\) (dividing by \(x^2\)), we get:
\[1 - z - z^2 = -z^2((\frac{1}{z})^2 + \frac{1}{z} - 1) = -z^2(z-\frac{1}{\phi})(z-\frac{1}{\hat{\phi}})\]Therefore:
\[\mathcal{F}(z) = \frac{z}{(1-\phi z)(1-\hat{\phi}z)}\]Using partial fractions:
\[\frac{z}{(1-\phi z)(1-\hat{\phi}z)} = \frac{A}{1-\phi z} + \frac{B}{1-\hat{\phi}z}\]Solving: \(A = \frac{1}{\sqrt{5}}, B = -\frac{1}{\sqrt{5}}\)
\[\mathcal{F}(z) = \frac{1}{\sqrt{5}}\left(\frac{1}{1-\phi z} - \frac{1}{1-\hat{\phi}z}\right)\]
C
Using the geometric series \(\frac{1}{1-x} = \sum_{i=0}^{\infty} x^i\):
\[\begin{align*} \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_{i=0}^{\infty}(\phi z)^i - \sum_{i=0}^{\infty}(\hat{\phi} z)^i\right)\\ &= \sum_{i=0}^{\infty} \frac{1}{\sqrt{5}}(\phi^i - \hat{\phi}^i)z^i \end{align*}\]D
From part C, the coefficient of \(z^i\) in \(\mathcal{F}(z)\) is:
\[F_i = \frac{\phi^i - \hat{\phi}^i}{\sqrt{5}}\]Since \(\|\hat{\phi}\| = \left\|\frac{1-\sqrt{5}}{2}\right\| = \frac{\sqrt{5}-1}{2} \approx 0.618 < 1\), we have \(\|\hat{\phi}^i\| < 1\) for all \(i \ge 1\).
Therefore: \(\|F_i - \frac{\phi^i}{\sqrt{5}}\| = \frac{\|\hat{\phi}\|^i}{\sqrt{5}} < \frac{1}{\sqrt{5}} < 0.5\)
This means \(F_i\) is the nearest integer to \(\phi^i/\sqrt{5}\).
Closed form: \(F_i = \left\lfloor \frac{\phi^i}{\sqrt{5}} + \frac{1}{2} \right\rfloor\)