4-5 Fibonacci numbers

This problem develops properties of the Fibonacci numbers, which are defined by recurrence (3.31) on page 69. We’ll explore 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\cr & = 0+z+z^2+2z^3+3z^4+5z^5+8z^6+13z^7+21z^8+\cdots,\cr \end{aligned} $$ where $F_i$ is the $i$th Fibonaccci nunber.

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

b. Show that

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

where $\phi$ is the golden ratio, and $\hat{\phi}$ is its conjugatr(see page 69).

c. Show that

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

You may use without proof the generating-function version of equation (A.7) on page 1142, $\sum_{k=0}^{\infty} x^k=1/(1-x)$. Because this equation involves a generating function, $x$ is formal variable, not a real-valued variable, so that you don’t have to worry about convergence of the summation or about the requirement in equation (A.7) that $|x|<1$, which doesn’t make sense here.

d. Use part (c) to prove that $F_i=\phi^i/\sqrt{5}$ for $i>0$, rounded to the nearest integer.

(Hint: Observe that $|\hat\phi<1|$.)

e Prove that $F_{i+2}\geq \phi^{i}$ for $i\geq 0$.

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_iz^i\cr & = z+\sum_{i=1}^{\infty}F_{i-1}z^i + \sum_{i=2}^{\infty}F_{i-2}z^i\cr & = z+F_{0}z^1 + \sum_{i=2}^{\infty}(F_{i-2}+F_{i-1})z^i\cr & = z+0 + \sum_{i=2}^{\infty}F_{i}z^i\cr & =\sum_{i=0}^{\infty}F_{i}z^i\cr & =\mathcal{F}(z)\cr \end{aligned} $$

b

$$ \begin{aligned} &\mathcal{F}(z)=z+z\mathcal{F}(z)+z^2\mathcal{F}(z)\cr \implies & \mathcal{F}(z) = \frac{z}{1-z-z^2}\cr & \phi\hat{\phi}=-1;\phi + \hat{\phi}=1;\phi - \hat{\phi}=\sqrt{5}\cr \implies & \mathcal{F}(z) = \frac{z}{1-(\phi + \hat{\phi})z-(-\phi\hat{\phi})z^2}\cr \implies & \mathcal{F}(z) = \frac{z}{(1-\phi z)(1-\hat\phi z)}\cr \implies & \mathcal{F}(z) = \frac{1}{\sqrt{5}}\frac{(\phi - \hat{\phi}) z}{(1-\phi z)(1-\hat\phi z)}\cr \implies & \mathcal{F}(z) = \frac{1}{\sqrt{5}}(\frac{1}{1-\phi z}-\frac{1}{1-\hat\phi z})\cr \end{aligned} $$

c

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

d

$$ \begin{aligned} F_{i} & =\frac{1}{\sqrt{5}}(\phi^{i}-\hat{\phi}^i)\cr & = \frac{\phi^{i}}{\sqrt{5}}-\frac{\hat{\phi}^i}{\sqrt{5}}\cr & \because |\hat{\phi}^i|<1 \therefore |\hat{\phi}^i/\sqrt{5}|<0.5\cr \implies & F_{i}=round(\frac{\phi^{i}}{\sqrt{5}})\cr \end{aligned} $$

e

$$ \begin{aligned} F_{2} & =1\geq\phi^{0}=1\cr F_{3} & =2\geq\phi^{1}=\frac{1+\sqrt{5}}{2}\cr F_{i+2} & = F_{i+1}+F_{i}\cr & \geq \phi^{i-1}+\phi^{i-2}\cr & =\phi^{i-2}(\phi+1)\cr & =\phi^{i-2}(\phi^2)\cr & = \phi^{i}\cr \end{aligned} $$