SICP Exercise 1.13

Question

Prove that $Fib(n)$ is the closest integer to $\phi^n/\sqrt{5}$, where $\phi=(1+\sqrt{5})/2$. Hint: Let $\psi=(1-\sqrt{5})/2$. Use induction and the definition of the Fibonacci numbers (see section 1.2.2) to prove that $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$.

Answer

As instructed in the question, we are proving $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$ first.

First, assume a simple base case of $n=0$. Let us prove that the theorem holds:

$$Fib(0)=\frac{\phi^0-\psi^0}{\sqrt5}$$

Of course, $Fib(0)=0$:

$$0=\frac{\phi^0-\psi^0}{\sqrt5}$$ $$0=\frac{1-1}{\sqrt5}$$ $$0=\frac{0}{\sqrt5}$$ $$0=0$$ $$\tag*{$\Box$}$$

Having proven the base case of $n=0$, we should prove the base case $n=1$ as well, since these two numbers are not themselves the result of a Fibonacci operation.

$$Fib(1)=\frac{\phi^1-\psi^1}{\sqrt5}$$ $$1=\frac{\phi-\psi}{\sqrt5}$$ $$1=\frac{\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}}{\sqrt5}$$ $$1=\frac{\frac{1+\sqrt5-1+\sqrt5}{2}}{\sqrt5}$$ $$1=\frac{\frac{2\sqrt5}{2}}{\sqrt5}$$ $$1=\frac{\sqrt5}{\sqrt5}$$ $$1=1$$ $$\tag*{$\Box$}$$

We can now move on to proving the case $n=k+1$.

Remember the definition of the Fibonacci sequence: $Fib(n)=Fib(n-1)+Fib(n-2)$. Let us replace $n$ with $k+1$:

$$Fib(k+1)=Fib(k)+Fib(k-1)$$

We will use this definition to carry out the proof. Remember the equation $Fib(n)=(\phi^n-\psi^n)/\sqrt{5}$ which we are trying to prove. From this follows:

$$Fib(k+1)=\frac{\phi^k-\psi^k}{\sqrt5}+\frac{\phi^{k-1}-\psi^{k-1}}{\sqrt5}$$ $$Fib(k+1)=\frac{\phi^k+\phi^{k-1}-\psi^k-\psi^{k-1}}{\sqrt5}$$ $$Fib(k+1)=\frac{\phi^{k-1}(\phi+1)-\psi^{k-1}(\psi+1)}{\sqrt5}$$

Remember that $\phi+1=\phi^2$ and $\psi+1=\psi^2$:

$$Fib(k+1)=\frac{\phi^{k-1}\phi^2-\psi^{k-1}\psi^2}{\sqrt5}$$ $$Fib(k+1)=\frac{\phi^{k+1}-\psi^{k+1}}{\sqrt5}$$ $$\tag*{$\Box$}$$

This, of course, is equivalent to the function definition. The equation is proven by induction.

Now, let’s prove that $Fib(n)$ is always the closest integer to $\frac{\phi^n}{\sqrt5}$. A mathematical way to phrase this would be as follows:

$$|Fib(n)-\frac{\phi^n}{\sqrt5}|\lt\frac{1}{2}$$

As we just proved, $Fib(n)$ is equivalent to $\frac{\phi^n-\psi^n}{\sqrt5}$. So let us rewrite the above equation accordingly:

$$|\frac{\phi^n-\psi^n}{\sqrt5}-\frac{\phi^n}{\sqrt5}|\lt\frac{1}{2}$$ $$|\frac{\phi^n-\psi^n-\phi^n}{\sqrt5}|\lt\frac{1}{2}$$ $$|\frac{-\psi^n}{\sqrt5}|\lt\frac{1}{2}$$ $$|\frac{\psi^n}{\sqrt5}|\lt\frac{1}{2}$$

The actual value of $\psi$ is $\approx-0.6180$. So, taking the $n$-th power of $\psi$ ($n$ being a positive integer), the value of $\psi^n$ will approach $0$. This means that the maximum value that $\psi^n$ can hold is $\psi^0$ which is $1$.

From this follows that the maximum value of the left side of our equation is $\frac{1}{\sqrt5}$. This equates to $\approx0.4472$, which is less than $\frac{1}{2}$. Since the result of the left side will only get smaller than this, the statement is proven.