SICP Exercise 1.13

Question

Prove that $Fib(n)$ is the closest integer to ${\varphi }^n/\sqrt{5}$, where $\varphi =(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)=({\varphi }^n-{\psi }^n)/\sqrt{5}$.

Answer

As instructed in the question, we are proving $Fib(n)=({\varphi }^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{{\varphi }^0-{\psi }^0}{\sqrt{5}}$$

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

$$0=\frac{{\varphi }^0-{\psi }^0}{\sqrt{5}}$$ $$0=\frac{1-1}{\sqrt{5}}$$ $$0=\frac{0}{\sqrt{5}}$$ $$0=0$$ $$\begin{array}{}◻& \end{array}$$

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{{\varphi }^1-{\psi }^1}{\sqrt{5}}$$ $$1=\frac{\varphi -\psi }{\sqrt{5}}$$ $$1=\frac{\frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}}{\sqrt{5}}$$ $$1=\frac{\frac{1+\sqrt{5}-1+\sqrt{5}}{2}}{\sqrt{5}}$$ $$1=\frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}}$$ $$1=\frac{\sqrt{5}}{\sqrt{5}}$$ $$1=1$$ $$\begin{array}{}◻& \end{array}$$

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)=({\varphi }^n-{\psi }^n)/\sqrt{5}$ which we are trying to prove. From this follows:

$$Fib(k+1)=\frac{{\varphi }^k-{\psi }^k}{\sqrt{5}}+\frac{{\varphi }^{k-1}-{\psi }^{k-1}}{\sqrt{5}}$$ $$Fib(k+1)=\frac{{\varphi }^k+{\varphi }^{k-1}-{\psi }^k-{\psi }^{k-1}}{\sqrt{5}}$$ $$Fib(k+1)=\frac{{\varphi }^{k-1}(\varphi +1)-{\psi }^{k-1}(\psi +1)}{\sqrt{5}}$$

Remember that $\varphi +1={\varphi }^2$ and $\psi +1={\psi }^2$:

$$Fib(k+1)=\frac{{\varphi }^{k-1}{\varphi }^2-{\psi }^{k-1}{\psi }^2}{\sqrt{5}}$$ $$Fib(k+1)=\frac{{\varphi }^{k+1}-{\psi }^{k+1}}{\sqrt{5}}$$ $$\begin{array}{}◻& \end{array}$$

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{{\varphi }^n}{\sqrt{5}}$. A mathematical way to phrase this would be as follows:

$$|Fib(n)-\frac{{\varphi }^n}{\sqrt{5}}|<\frac{1}{2}$$

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

$$|\frac{{\varphi }^n-{\psi }^n}{\sqrt{5}}-\frac{{\varphi }^n}{\sqrt{5}}|<\frac{1}{2}$$ $$|\frac{{\varphi }^n-{\psi }^n-{\varphi }^n}{\sqrt{5}}|<\frac{1}{2}$$ $$|\frac{-{\psi }^n}{\sqrt{5}}|<\frac{1}{2}$$ $$|\frac{{\psi }^n}{\sqrt{5}}|<\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}{\sqrt{5}}$. This equates to $\approx 0.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.