## SICP – A Proof for Exercise 1.13

Exercise 1.13 in Section 1.2.2 asks for a proof that $Fib(n)$ is the closest integer to ${\phi^n}/{\sqrt{5}}$, where $\phi=(1+\sqrt{5})/2$.

Proof Idea: To show that $Fib(n)$ is the closest integer to ${\phi^n}/{\sqrt{5}}$ we simply need to show that $|Fib(n) - \phi^n/\sqrt{5}| < 1/2$ for all $n \geq 0$. We will establish the result by proving two lemmas.

Lemma 1: $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$ for all $n \geq 0$.

Lemma 2: $|\psi^n|/\sqrt{5} < 1/2$ for all $n \geq 0$.

Notice that if Lemma 1 and Lemma 2 are true it will follow that $|Fib(n) - \phi^n/\sqrt{5}| = |(\phi^n - \psi^n)/\sqrt{5} - \phi^n/\sqrt{5}| = |\psi^n|/\sqrt{5} < 1/2$ for all $n \geq 0$.

It remains to be shown that Lemma 1 and Lemma 2 are indeed true.

Proof of Lemma 1: We will prove the result by Induction on $n$. When n = 0 and n = 1, the result follows trivially. Let $n \geq 0$ and suppose the result holds for $n$ and $n+1$. Consider, $Fib(n+2)$. By definition, $Fib(n+2) = Fib(n+1) + Fib(n)$. Then by using the Induction Hypothesis, it follows that

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

which can be further reduced to

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

Since $\phi^2 = \phi + 1$ and $\psi^2 = \psi + 1$, the result holds for $Fib(n+2)$. Therefore, by Induction, $Fib(n) = (\phi^n - \psi^n)/\sqrt{5}$ for all $n \geq 0$.

Q.E.D.

Proof of Lemma 2: $\sqrt{5} > 2$ implies that $\frac{1}{\sqrt{5}} < \frac{1}{2}$, i.e. $\frac{|\psi^0|}{\sqrt{5}} < \frac{1}{2}$. Also, $\sqrt{5} < 3$ implies that $\sqrt{5} - 1 < 2$ which implies that $\frac{\sqrt{5} - 1}{2} < 1$. So, $|\psi^n| \cdot \frac{\sqrt{5} - 1}{2} < |\psi^n|$ for any $n \geq 0$. But, $|\psi^n| \cdot \frac{\sqrt{5} - 1}{2} = |\psi^{n+1}|$. Hence, $|\psi^{n+1}| < |\psi^n|$ for all $n \geq 0$ and it trivially follows that $\frac{|\psi^{n+1}|}{\sqrt{5}} < \frac{|\psi^n|}{\sqrt{5}}$ for all $n \geq 0$. Since $\frac{|\psi^0|}{\sqrt{5}} < \frac{1}{2}$ and $\frac{|\psi^n|}{\sqrt{5}}$ decreases as $n$ increases, we can conclude that $\frac{|\psi^n|}{\sqrt{5}} < \frac{1}{2}$ for all $n \geq 0$.

Q.E.D.

As planned, this completes the proof that $Fib(n)$ is the closest integer to ${\phi^n}/{\sqrt{5}}$.