SICP – A Proof for Exercise 1.13 | Incongruent Thoughts

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