## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 1.13

## Problem

Prove that *Fib(n)* is the closest integer to

<math> \phi^n/\sqrt{5} </math>,

where

<math> \phi=(1+\sqrt{5})/2 </math>.

Hint: Let

<math> \psi=(1-\sqrt{5})/2 </math>

and use induction and the definition of the Fibonacci numbers to prove that

<math> Fib(n)=(\phi^n-\psi^n)/\sqrt{5} </math>.

## Solution

This exercise is off-topic, having little or nothing to do with the subject of the book, but a proof by induction follows. We must show that the equality holds true for *n*=0 and *n*=1, and then show that if we assume it's true for *n*=*i*, it must also be true for *n*=*i*+1.

<math> Fib(0)=0 </math>

and

<math> (\phi^0-\psi^0)/\sqrt{5}=0 </math>

Also:

<math> Fib(1)=1 </math>

and

<math> (\phi-\psi)/\sqrt{5}=\sqrt{5}/\sqrt{5}=1 </math>

Now, by induction, we assume that

<math> Fib(n)=(\phi^n-\psi^n)/\sqrt{5} </math>

is true for all *n* up to and including <math>n=i+1</math>. We must now show that

<math> Fib(i+2)=(\phi^{i+2}-\psi^{i+2})/\sqrt{5}. </math>

We know, by the definition of *Fib(n)*, that

<math> Fib(i+2)=Fib(i+1)+Fib(i) </math>

Then by substitution:

<math> Fib(i+2)=(\phi^{i+1}-\psi^{i+1})/\sqrt{5}+(\phi^i-\psi^i)/\sqrt{5}

=(\phi^{i+1}+\phi^i-\psi^{i+1}-\psi^i)/\sqrt{5} =(\phi^i(1+\phi)-\psi^i(1+\psi))/\sqrt{5}

</math>

Observe that

<math> 1+\phi=1+(1+\sqrt{5})/2

=(3+\sqrt{5})/2

</math>

and also

<math> \phi^2=((1+\sqrt{5})/2)^2

=(1+2\sqrt{5}+5)/4 =(6+2\sqrt{5})/4 =(3+\sqrt{5})/2 =1+\phi

</math>

Similarly, we can also easily prove that

<math> 1+\psi=\psi^2 </math>

Then, substituting back into the original equation we get:

<math> Fib(i+2)=(\phi^i\phi^2-\psi^i\psi^2)/\sqrt{5}

=(\phi^{i+2}-\psi^{i+2})/\sqrt{5}

</math>

which proves, by induction, that

<math> Fib(n)=(\phi^n-\psi^n)/\sqrt{5} </math>

## Credits

Hank Meuret pointed out a missing square in the <math>\phi^2</math> equation.