TAOCP 1.2.8 Exercise 28
From the closed form expression (14) for the Fibonacci numbers, we have F_n = \frac{1}{\sqrt{5}}\bigl(\phi^n - \hat{\phi}^n\bigr), \qquad \hat{\phi} = 1-\phi = \frac{1}{2}(1-\sqrt{5}).
Section 1.2.8: Fibonacci Numbers
Exercise 28. [M21] What is $F_{n+1}-\phi F_n$?
Verified: no
Solve time: -
Solution
From the closed form expression (14) for the Fibonacci numbers, we have
$$ F_n = \frac{1}{\sqrt{5}}\bigl(\phi^n - \hat{\phi}^n\bigr), \qquad \hat{\phi} = 1-\phi = \frac{1}{2}(1-\sqrt{5}). $$
We want to compute $F_{n+1} - \phi F_n$. Substituting the closed forms gives
$$ \begin{aligned} F_{n+1} - \phi F_n &= \frac{1}{\sqrt{5}}\bigl(\phi^{n+1} - \hat{\phi}^{,n+1}\bigr) - \phi \cdot \frac{1}{\sqrt{5}}\bigl(\phi^n - \hat{\phi}^n\bigr) \ &= \frac{1}{\sqrt{5}}\Bigl(\phi^{n+1} - \hat{\phi}^{,n+1} - \phi^{,n+1} + \phi \hat{\phi}^n\Bigr) \ &= \frac{1}{\sqrt{5}}\Bigl(\phi \hat{\phi}^n - \hat{\phi}^{,n+1}\Bigr) \ &= \frac{1}{\sqrt{5}}\Bigl(\phi \hat{\phi}^n - \hat{\phi} \hat{\phi}^n\Bigr) \ &= \frac{1}{\sqrt{5}}(\phi - \hat{\phi}) \hat{\phi}^n. \end{aligned} $$
From the definitions of $\phi$ and $\hat{\phi}$, we have
$$ \phi - \hat{\phi} = \phi - (1-\phi) = 2\phi - 1 = \sqrt{5}. $$
Substituting this into the previous expression yields
$$ F_{n+1} - \phi F_n = \frac{\sqrt{5}}{\sqrt{5}} \hat{\phi}^n = \hat{\phi}^n. $$
Thus we have
$$ \boxed{F_{n+1} - \phi F_n = \hat{\phi}^n}. $$
This completes the proof.
∎