SICP Exercise 1.13

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.

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 \(,\)$ { { } } = { { } } = { { } } = { { 4} } = { { 4 { } } } = 1 = { Fib(2) } $$

Inductive step

Assume that the relation we seek to prove holds for $ n = m $ and $ n = m - 1 $ for some $ m $. 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 $ {}^{m-1} ( + 1 ) $ 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 $ {}^{m-1} ( + 1 ) = {}^{m+1} $.

Now plugging in these values for $ {}^{m-1} ( + 1 ) \(</span> and <span>\) {}^{m-1} ( + 1 ) $ 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) = { { } } \(</span>, which completes our inductive proof of the relation <span>\) Fib(n) = { { } } $.

Final proof

Now to prove that $ Fib(n) = nint ( { } ) $ . Note that when we say \(N\) is the nearest integer to \(x\), we are implying that $ N - x < \(</span>. We have already proved that <span>\) Fib(n) = { { } } $. 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) \(</span> is the nearest integer to <span>\) { } \(</span>, the absolute value of their difference must be less than <span>\) $. That is,

So, to prove that $ Fib(n) = nint ( { } ) \(</span>, it suffices to prove that <span>\) { } $.

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}^{+} \(</span>. This means that the fraction <span>\) $ 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}\).

.