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\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用