SICP Exercise 1.13
The Fibonacci sequence is given by,
Exercise 1.13 in SICP asks you to prove that the $n^{th}$ Fibonacci number $(n = 0, 1,…)$ is equal to the closest integer to $\frac{ { \phi } ^ { n } } { \sqrt 5 }$, where ${ \phi } = { \frac { 1 + { \sqrt 5 } } { 2 } }$. The given hint is to use ${ \psi } = { \frac { 1 - { \sqrt 5 } } { 2 } }$ to prove that ${Fib(n)} = { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } }$.
Some will recognize the constant $\phi$ as the Golden Ratio. While knowing this fact allows one to use some useful properties of $\phi$ and $\psi$, I am not going to use them in my proof.
We will first prove by induction that
And then use this result to prove that
Where \(nint(x)\) is the nearest integer to \(x\).
Inductive base cases
For \(n = 0\) ,
For \(n = 1\) ,
For \(n = 2\) ,
Inductive step
Assume that the relation we seek to prove holds for $ n = m $ and $ n = m - 1 $ for some $ m \gt 2 $. That is,
We need to prove that,
Now,
Let’s look at the term $ {\phi}^{m-1} \left( \phi + 1 \right) $ separately.
Multiplying numerator and denominator by $2$, we have
Similarly, it can be deduced that $ {\psi}^{m-1} \left( \psi + 1 \right) = {\psi}^{m+1} $.
Now plugging in these values for $ {\phi}^{m-1} \left( \phi + 1 \right) $ and $ {\psi}^{m-1} \left( \psi + 1 \right) $ in \ref{eq1}, we have
Hence, we have just proved that $ Fib(m+1) = { \frac { {\phi}^{m+1} - {\psi}^{m+1} } { \sqrt 5 } } $, which completes our inductive proof of the relation $ Fib(n) = { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } } $.
Final proof
Now to prove that $ Fib(n) = nint \left( \frac { {\phi}^{n} } { \sqrt 5 } \right) $ . Note that when we say $N$ is the nearest integer to $x$, we are implying that $ \lvert N - x \rvert < \frac{1}{2} $. We have already proved that $ Fib(n) = { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } } $. Or,
or,
Taking absolute value on both sides,
As noted before, if $ Fib(n) $ is the nearest integer to $ \frac{ {\phi}^{n} } { \sqrt 5 } $, the absolute value of their difference must be less than $ \frac{1}{2} $. That is,
So, to prove that $ Fib(n) = nint \left( \frac { {\phi}^{n} } { \sqrt 5 } \right) $, it suffices to prove that $ \lvert \frac { {\psi}^{n} } { \sqrt 5 } \rvert \lt \frac {1}{2} $.
Let’s print out the first 10 values of \(\lvert \frac { {\psi}^{n} } {\sqrt 5} \rvert\) for $ n = (0,1…9) $.
> (map (lambda (n)
(abs (/ (^ psi n)
(sqrt 5))))
'(0 1 2 3 4 5 6 7 8 9))
;(.4472135954999579 .27639320225002106 .17082039324993692 .10557280900008414
.06524758424985282 4.0325224750231356e-2 2.4922359499621467e-2 1.5402865250609892e-2
.00951949424901158 5.883371001598312e-3)
Clearly, these are all less than $ 0.5 $. But we can prove this fact using induction.
For $ n = 0 $,
Here, we used that fact that $\sqrt 5 \gt \sqrt 4$. We do not need the exact value of $\sqrt 5$. We just need to know that it is greater than 2, but not 3, which we write as $ {2}^{+} $. This means that the fraction $ \frac {1}{\sqrt 5} $ has a denominator of more than $2$, making the fraction itself less than $\frac {1}{2}$.
For $ n = 1 $,
Now let us assume that for some $n = m$, $\lvert \frac { {\psi}^{m} } { \sqrt 5 } \rvert \lt \frac {1}{2}$. Using this, we need to prove that $\lvert \frac { {\psi}^{m+1} } { \sqrt 5 } \rvert \lt \frac {1}{2}$.
We know that $ \lvert \frac { {\psi}^{m} } { \sqrt 5 } \rvert \lt \frac {1}{2} $, which was our assumption in the inductive step. But $ \lvert \psi \rvert \approx \lvert -.6180339887498949 \rvert = .6180339887498949 \lt 1$. A number less than half times a number less than $1$ has to result in a number less than half. That is, ${\frac {1}{2}}^{-} \times {1}^{-} = {\frac {1}{2}}^{-}$. Which means,
.
This completes our proof of the relation $ \lvert \frac { {\psi}^{n} } { \sqrt 5 } \rvert \lt \frac {1}{2} \forall n \ge 0 $. Which immediately leads to the final proof that,