Exercise 1.13
The constants \(φ\) and \(ψ\) are the solutions to the golden ration equation \(x + 1 = x^2\):
\[
\phi = \frac{1+\sqrt{5}}{2}, \ \ \ \ \phi = \frac{1-\sqrt{5}}{2}.
\]
The Fibonacci sequence is defined recursively by
\[
\begin{aligned}
\operatorname{Fib}(0) &= 0,\\
\operatorname{Fib}(1) &= 1,\\
\operatorname{Fib}(n) &= \operatorname{Fib}(n-1) + \operatorname{Fib}(n-2).
\end{aligned}
\]
Lemma. \(\operatorname{Fib}(n)\) is equal to \(f(n) = \frac{φ^n - ψ^n}{\sqrt{5}}\).
Proof. First, we will demonstrate three base cases. When \(n = 0\),
\[
f(0) = \frac{φ^0 - ψ^0}{\sqrt{5}} = \frac{1-1}{\sqrt{5}} = 0
\]
When \(n = 1\),
\[
f(1)=\frac{φ^1 - ψ^1}{\sqrt{5}} = \frac{\frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}}{\sqrt{5}} = \frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}} = 1
\]
When \(n = 2\),
\[
\begin{aligned}
f(2) &= \frac{φ^2 - ψ^2}{\sqrt{5}}\\
&= \frac{(\frac{1+\sqrt{5}}{2})^2 - (\frac{1-\sqrt{5}}{2})^2}{\sqrt{5}}\\
&= \frac{\frac{(1+\sqrt{5})^2 - (1 - \sqrt{5})^2}{4}}{\sqrt{5}} \\
&= \frac{((1+\sqrt{5}) - (1 - \sqrt{5})) \ ((1+\sqrt{5}) + (1-\sqrt{5}))}{4 \sqrt{5}} \\
&= \frac{(2\sqrt{5})(2)}{4\sqrt{5}} \\
&= 1.
\end{aligned}
\]
Now comes the inductive step:
\[
\begin{aligned}
f(n-1) + f(n-2) &= \frac{φ^{n-1} - ψ^{n-1}}{\sqrt{5}} + \frac{φ^{n-2} - ψ^{n-2}}{\sqrt{5}} \\
&= \frac{(φ^{n-1} + φ^{n-2}) - (ψ^{n-1} + ψ^{n-2})}{\sqrt{5}} \\
&= \frac{φ^n \ (φ^{-1} + φ^{-2}) - ψ^n \ (ψ^{-1} + ψ^{-2})}{\sqrt{5}} \\
&= \frac{φ^nφ^{-1} \ (1 + φ^{-1}) - ψ^nψ^{-1} \ (1 + ψ^{-1})}{\sqrt{5}} \\
&= \frac{φ^nφ^{-1} \ (φ) - ψ^nψ^{-1} \ (ψ)}{\sqrt{5}} \\
&= \frac{φ^n - ψ^n}{\sqrt{5}} \\
&= f(n).
\end{aligned}
\]
By induction, \(f(n) = \operatorname{Fib}(n)\) for all \(n\). \(\blacksquare\)
Theorem. \(\operatorname{Fib}(n)\) is the closest integer to \(\frac{φ^n}{\sqrt{5}}\), where \(φ = \frac{1 + \sqrt{5}}{2}\).
Proof. It suffices to show that the absolute difference is less than one half:
\[
\begin{aligned}
\left\lvert \operatorname{Fib}(n) - \frac{φ^n}{\sqrt{5}} \right\rvert &< \frac{1}{2} \\
\left\lvert \frac{φ^n - ψ^n}{\sqrt{5}}-\frac{φ^n}{\sqrt{5}}\right\rvert &< \frac{1}{2} \\
\left\lvert -\frac{ψ^n}{\sqrt{5}}\right\rvert &< \frac{1}{2} \\
\frac{|-ψ^n|}{\sqrt{5}} &< \frac{1}{2} \\
|ψ|^n &< \frac{\sqrt{5}}{2}.
\end{aligned}
\]
Since \(|ψ| < 0.619 < 1\), we have \(|ψ|^n < 1 < \frac{\sqrt{5}}{2}\) for all \(n\). \(\blacksquare\)