# Fibonacci numbers and the golden ratio

7 April 2016 · 3 minute read · technical, rc, math and sicp

SICP is one of the standard books people study at RC. It’s definitely pretty cool, and something I’ve had a bit of experience with since getting half way through the 1986 lectures based on the book.

We have a study group for SICP that I have been involved with. Today one of the problems we looked at was 1.13, which is as follows:

Prove that $Fib(n)$ is the closest integer to $\frac{\phi^n}{\sqrt{5}}$, where $\phi = \frac{1 + \sqrt{5}}{2}$.

Hint: Let $\psi = \frac{1 - \sqrt{5}}{2}$. Use induction and the definition of the Fibonacci numbers to prove that $Fib(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$.

I happened to be the whiteboard person for this problem, and I thought the solution was a neat bit of induction. We are working (perhaps obviously) exclusively in the non-negative integers here.

We begin with some basic definitions:

$$Fib(n) = \begin{cases} 0 & \text{if }n = 0 \\\ 1 & \text{if }n = 1 \\\ Fib(n - 1) + Fib(n - 2) & \text{otherwise} \end{cases} \\\ \phi = \frac{1 + \sqrt{5}}{2} \\\ \psi = \frac{1 - \sqrt{5}}{2}$$

Next, as suggested, we attempt to prove that

$$$$f(n) = Fib(n)$$$$

given:

$$f(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

Fairly obviously:

$$f(0) = \frac{\phi^0 - \psi^0}{\sqrt{5}} = \frac{1 - 1}{\sqrt{5}} = 0$$

and

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

Now, the recursive step.

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

Assume that $(1)$ is true, and we can replace this with:

\begin{align*} Fib(n + 1) & = Fib(n) + Fib(n - 1) \\\ & = f(n) + f(n-1) \\\ & = \frac{\phi^n - \psi^n}{\sqrt{5}} + \frac{\phi^{n-1} - \psi^{n-1}}{\sqrt{5}} \\\ & = \frac{1}{\sqrt{5}} \lgroup\phi^{n-1}(\phi + 1) - \psi^{n-1}(\psi + 1)\rgroup \\\ & = \frac{1}{\sqrt{5}} \lgroup\phi^{n-1}\phi^2 - \psi^{n-1}\psi^2\rgroup \\\ & = \frac{1}{\sqrt{5}} \lgroup\phi^{n+1} - \psi^{n+1}\rgroup \\\ & = f(n + 1) \end{align*}

We therefore have:

$$Fib(n + 1) = f(n + 1)\text{ given }Fib(n) = f(n)\text{,} \\\ Fib(0) = f(0)\text{ and } \\\ Fib(1) = f(1)$$

meaning that for all non-negative integers n:

$$Fib(n) = f(n) = \frac{\phi^n - \psi^n}{\sqrt{5}}$$

The only perhaps non-intuitive step so far is to say that: $\phi + 1 = \phi^2$ and $\psi + 1 = \psi^2$.

This can be easily demonstrated:

\begin{align*} \phi^2 & = \lgroup\frac{1 + \sqrt{5}}{2}\rgroup{}^2 \\\ & = \frac{1 + 2\sqrt(5) + 5}{4} \\\ & = \frac{6 + 2\sqrt(5)}{4} \\\ & = \frac{3 + \sqrt(5)}{2} \\\ & = \frac{1 + \sqrt(5)}{2} + 1 \end{align*}

and similarly for $\psi^2$.

This is not quite the end of the problem though. We still need to show that $Fib(n)$ is the closest integer to $\frac{\phi^n}{\sqrt{5}}$.

\begin{align*} Fib(n) - \frac{\phi^n}{\sqrt{5}} & = \frac{\phi^n - \psi^n}{\sqrt{5}} - \frac{\phi^n}{\sqrt{5}} \\\ & = \frac{\phi^n - \psi^n - \phi^n}{\sqrt{5}} \\\ & = \frac{\psi^n}{\sqrt{5}} \\\ & = \frac{\lgroup\frac{1-\sqrt{5}}{2}\rgroup{}^n}{\sqrt{5}} \\\ & = \frac{\lgroup{}1-\sqrt{5}\rgroup{}^n}{2^n\sqrt{5}} \\\ & \approx \frac{-1.236^n}{2^n\sqrt{5}} \end{align*}

For $n=1$ this is approximately $0.276 < 0.5$, and for $n=0$ this is approximately $0.447$. It is clear that $2^n$ grows faster than $(1 - \sqrt(5))^n$ and so the upper bound of $\lvert{}Fib(n) - \frac{\phi^n}{\sqrt{5}}\rvert{}$ is $0.447$.

As such, we can say that $\lvert{}Fib(n) - \frac{\phi^n}{\sqrt{5}}\rvert{} < 0.5$ for all non-negative integers $n$. $\Box$