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,