The Fibonacci sequence is given by,

$$ Fib(n) = { \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ Fib(n - 1) + Fib(n - 2) & n \gt 1 \end{cases} } $$

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

$$ {Fib(n)} = { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } } $$

And then use this result to prove that

$$ {Fib(n)} = nint \left( { \frac{ { \phi } ^ { n } } { \sqrt 5 } } \right) $$

Where \(nint(x)\) is the nearest integer to \(x\).

Inductive base cases

For \(n = 0\) ,

$$ { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } } = { \frac { {\phi}^{0} - {\psi}^{0} } { \sqrt 5 } } = { \frac { 1 - 1 } { \sqrt 5 } } = 0 = { Fib(0) } $$

For \(n = 1\) ,

$$ { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } } = { \frac { {\phi}^{1} - {\psi}^{1} } { \sqrt 5 } } = { \frac { {\phi} - {\psi} } { \sqrt 5 } } = { \frac { { \frac { 1 + { \sqrt 5 } } { 2 } } - { \frac { 1 - { \sqrt 5 } } { 2 } } } { \sqrt 5 } } = { \frac { 2 { \sqrt 5 } } { 2 { \sqrt 5 } } } = 1 = { Fib(1) } $$

For \(n = 2\) ,

$$ { \frac { {\phi}^{n} - {\psi}^{n} } { \sqrt 5 } } = { \frac { {\phi}^{2} - {\psi}^{2} } { \sqrt 5 } } = { \frac { { { \left( { \frac { 1 + { \sqrt 5 } } { 2 } } \right) } ^ { 2 } } - { { \left( { \frac { 1 - { \sqrt 5 } } { 2 } } \right) } ^ { 2 } } } { \sqrt 5 } } = { \frac { 1 + 2\sqrt 5 + 5 - 1 + 2\sqrt 5 - 5 } { 4\sqrt 5} } = { \frac { 4 { \sqrt 5 } } { 4 { \sqrt 5 } } } = 1 = { Fib(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,

$$ Fib(m) = { \frac { {\phi}^{m} - {\psi}^{m} } { \sqrt 5 } }, Fib(m-1) = { \frac { {\phi}^{m-1} - {\psi}^{m-1} } { \sqrt 5 } } $$

We need to prove that,

$$ Fib(m+1) = { \frac { {\phi}^{m+1} - {\psi}^{m+1} } { \sqrt 5 } } $$

Now,

$$ Fib(m+1) = Fib(m) + Fib(m-1) $$
$$ = { { \frac { {\phi}^{m} - {\psi}^{m} } { \sqrt 5 } } + { \frac { {\phi}^{m-1} - {\psi}^{m-1} } { \sqrt 5 } } } $$
$$ = { \frac { \left( {\phi}^{m} + {\phi}^{m-1} \right) - \left( {\psi}^{m} + {\psi}^{m-1} \right) } { \sqrt 5 } } $$
$$ = { \frac { {\phi}^{m-1} \left( \phi + 1 \right) - {\psi}^{m-1} \left( \psi + 1 \right) } { \sqrt 5 } \tag{1}\label{eq1} } $$

Let’s look at the term $ {\phi}^{m-1} \left( \phi + 1 \right) $ separately.

$$ {\phi}^{m-1} \left( \phi + 1 \right) $$
$$ ={\phi}^{m-1} \left( { \frac {1 + \sqrt 5} {2}} + 1 \right) $$
$$ ={\phi}^{m-1} \left( { \frac {3 + \sqrt 5} {2} } \right) $$

Multiplying numerator and denominator by $2$, we have

$$ {\phi}^{m-1} \left( { \frac {6 + 2\sqrt 5} {4} } \right) $$
$$ ={\phi}^{m-1} \left( { \frac {1 + 2\sqrt 5 + 5} {4} } \right) ={\phi}^{m-1} \left( { \frac {1 + 2\sqrt 5 + {\left( \sqrt 5 \right)} ^ {2} } {4} } \right) $$
$$ ={\phi}^{m-1} \frac { { \left( 1 + \sqrt 5 \right) } ^ {2} } { {2}^{2} } ={\phi}^{m-1} { \left( { \frac { 1 + \sqrt 5 } { 2 } } \right) } ^ {2} $$
$$ ={\phi}^{m-1} {\phi}^{2} ={\phi}^{m+1} $$

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

$$ { \frac { {\phi}^{m-1} \left( \phi + 1 \right) - {\psi}^{m-1} \left( \psi + 1 \right) } { \sqrt 5 } } $$
$$ ={ \frac { {\phi}^{m+1} - {\psi}^{m+1} } { \sqrt 5 } } $$

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,

$$ Fib(n) = \frac{ {\phi}^{n} } { \sqrt 5 } - \frac{ {\psi}^{n} } { \sqrt 5 } $$

or,

$$ Fib(n) - \frac{ {\phi}^{n} } { \sqrt 5 } = \frac{ {\psi}^{n} } { \sqrt 5 } $$

Taking absolute value on both sides,

$$ \lvert { Fib(n) - \frac{ {\phi}^{n} } { \sqrt 5 } } \rvert = \lvert \frac{ {\psi}^{n} } { \sqrt 5 } \rvert $$

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,

$$ \lvert { Fib(n) - \frac{ {\phi}^{n} } { \sqrt 5 } } \rvert \lt \frac {1}{2} \implies \lvert \frac{ {\psi}^{n} } { \sqrt 5 } \rvert \lt \frac {1}{2} $$

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 $,

$$ \lvert \frac { {\psi}^{n} } { \sqrt 5 } \rvert = \lvert \frac { {\psi}^{0} } { \sqrt 5 } \rvert = \frac {1}{\sqrt 5} = \frac {1}{ {2}^{+} } \lt \frac {1}{2} $$

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 $,

$$ \lvert \frac { {\psi}^{n} } { \sqrt 5 } \rvert = \lvert \frac {\psi} { \sqrt 5 } \rvert = \lvert \frac { \frac {1 - \sqrt 5} {2} } { \sqrt 5 } \rvert = \frac {\sqrt 5 - 1} { 2 \sqrt 5 } = \frac {\sqrt 5 } { 2 \sqrt 5 } - \frac {1} { 2 \sqrt 5} = \left( \frac {1}{2} - \frac {1} { 2 \sqrt 5} \right) < \frac {1}{2} (\because \frac {1} {2 \sqrt 5} \gt 0) $$

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}$.

$$ \lvert \frac { {\psi}^{m+1} } { \sqrt 5 } \rvert =\lvert \frac { \psi {\psi}^{m} } { \sqrt 5 } \rvert =\lvert \psi \rvert \lvert \frac { {\psi}^{m} } { \sqrt 5 } \rvert $$

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,

$$ \lvert \psi \rvert \lvert \frac { {\psi}^{m} } { \sqrt 5 } \rvert \lt \frac {1}{2} \because \lvert \psi \rvert \lt 1, \lvert \frac { {\psi}^{m} } { \sqrt 5 } \rvert \lt \frac {1}{2} $$

.

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,

$$ Fib(n) = nint(\frac { {\phi}^{n} }{\sqrt 5}), \forall n \ge 0 \blacksquare $$