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