TAOCP 1.2.8 Exercise 10
From equation (14) we have the exact expression F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right), where
Section 1.2.8: Fibonacci Numbers
Exercise 10. [15] Is $\phi^n/\sqrt{5}$ greater than $F_n$ or less than $F_n$?
Verified: no
Solve time: -
Solution
From equation (14) we have the exact expression
$$ F_n = \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right), $$
where
$$ \hat{\phi} = 1 - \phi = -\frac{1}{\phi} = \frac{1}{2}(1 - \sqrt{5}). $$
Thus the difference between $\phi^n/\sqrt{5}$ and $F_n$ is
$$ \frac{\phi^n}{\sqrt{5}} - F_n = \frac{\phi^n}{\sqrt{5}} - \frac{1}{\sqrt{5}}\left(\phi^n - \hat{\phi}^n\right) = \frac{\hat{\phi}^n}{\sqrt{5}}. $$
Since $|\hat{\phi}| = |\frac{1-\sqrt{5}}{2}| = \frac{\sqrt{5}-1}{2} \approx 0.61803 < 1$ and $\hat{\phi} < 0$, we have
$$ \hat{\phi}^n = (-|\hat{\phi}|)^n = (-1)^n |\hat{\phi}|^n. $$
Therefore the difference $\phi^n/\sqrt{5} - F_n$ equals $(-1)^n |\hat{\phi}|^n / \sqrt{5}$. This quantity is positive when $n$ is even and negative when $n$ is odd. Equivalently:
- If $n$ is even, then $\phi^n/\sqrt{5} > F_n$.
- If $n$ is odd, then $\phi^n/\sqrt{5} < F_n$.
Hence $\phi^n/\sqrt{5}$ alternately overestimates and underestimates $F_n$ depending on the parity of $n$.
This completes the proof.
∎