# Finding the Fibonacci Numbers: The Formula

This is the third post in a series about an exact formula for the Fibonacci numbers, $F_n$, which are defined by the initial values $F_0 = 0, F_1 = 1$ and the recurrence relation $F_{n+1} = F_n + F_{n-1}$. We have made a lot of progress towards our goal. We discovered a connection between $x^2 - x - 1 = 0$, the golden ratio $\varphi = \dfrac{1+\sqrt{5}}{2}$, and the Fibonacci sequence by finding the almost-right formula $F_n \approx \varphi^n / 2.236$. We left off the last post with two important questions. We need to find out where this 2.236 constant is coming from, and we need to figure out how to fix the small error that lies between $F_n$ and $\varphi^n/2.236$.

Why Do We See 2.236?

First, we have to determine where 2.236 comes from. To get an idea, remember that the value of $\varphi^n / 2.236$ is very, very close to a whole number. Perhaps, then, by looking at the components of the number $\varphi$, we might be able to venture a guess. Remember that $\varphi$ is the golden ratio, $\dfrac{1+\sqrt{5}}{2}$. Looking at this, the most obvious non-whole number would be $\sqrt{5}$. Intuitively, in order to turn an expression that involves $\varphi$ into a whole number, you have to get rid of $\sqrt{5}$ somehow. Well, we ask, what value is $\sqrt{5}$? A calculator would show us pretty quickly that $\sqrt{5} \approx 2.236$. Surely that must be why we keep finding 2.236. It is too closely related $\varphi$ to be a coincidence. Our approximate formula, then is actually $F_n \approx \varphi^n / \sqrt{5}$.

What is the Leftover Error All About?

We are very, very close now. The only thing we haven’t figured out is how to predict the amount of error between $F_n$ and $\varphi^n / \sqrt{5}$. To do this, perhaps the same way we discovered the usefulness of $\varphi$ would help. Perhaps we can ask ourselves about how the amount of error changes over time, and using the same concepts as before, we can find a formula for the error.

This turns out to work. Using the table from the previous post, here is what we get.

The ratios of consecutive terms being basically the same, along with consecutive differences being basically the same sequence we started with, are tell-tale signs of an exponential sequence. The fact that the numbers get smaller rather than larger tells us that this number is somewhere between -1 and 1, since decimals multiplied by other decimals get closer to 0. The alternating behavior between + and – tells us that our number must be between -1 and 0. So, we’ve actually got a pretty narrow range. So, we take the guess that our error is exponential. Going along with the letter that is normally used for this number, I will call the ‘mystery number’ $\psi$, so our error is about $\psi^n$. The fifth column in the table, when read carefully, actually tells us that $1/\psi \approx - \varphi$. And, as it turns out, $\dfrac{-1}{\varphi}$ is the second solution to $x^2 - x - 1 = 0$ that we had neglected earlier! So, we make the guess that $\psi = \dfrac{1-\sqrt{5}}{2}$, and we save in our minds for later that $\psi = \dfrac{-1}{\varphi}$. It is also sensible to guess that (and computing tables as in the previous post confirms this) that we also have to divide by $\sqrt{5}$ to make a correction.

When you put everything together, you end up determining that the expression $\dfrac{\varphi^n}{\sqrt{5}} – \dfrac{\psi^n}{\sqrt{5}} = \dfrac{\varphi^n – \psi^n}{\sqrt{5}}$ appears to be exactly equal to $F_n$, at least for the first few values of $n$. It turns out that this is true, and we will now show exactly why this is true.

Theorem: For every whole number $n \geq 0$, the equation $F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}$

holds true, exactly. Furthermore, the value $\dfrac{\varphi^n}{\sqrt{5}}$ is correct when rounded to the nearest integer.

Proof: The proof runs along a fairly simple idea. Recall that the three equations $F_0 = 0, F_1 = 1$, and $F_{n+1} = F_n + F_{n-1}$ completely define all values of the Fibonacci sequence. What this means is that if any expression at all satisfies all three of those conditions, then that expression must be the Fibonacci sequence. We then must check all three of these for the expression $\dfrac{\varphi^n - \psi^n}{\sqrt{5}}$. Firstly, $\dfrac{\varphi^0 - \psi^0}{\sqrt{5}} = \dfrac{1 - 1}{\sqrt{5}} = 0$,

and so the first condition is true. Now, remembering that $\varphi = \dfrac{1+\sqrt{5}}{2}$ and $\psi = \dfrac{1 - \sqrt{5}}{2}$, $\dfrac{\varphi - \psi}{\sqrt{5}} = \dfrac{\dfrac{1+\sqrt{5}}{2} - \dfrac{1-\sqrt{5}}{2}}{\sqrt{5}} = \dfrac{\bigg( \dfrac{1 + \sqrt{5} - (1 -\sqrt{5})}{2}}{\sqrt{5}} = \dfrac{\sqrt{5}}{\sqrt{5}} = 1.$

We can now see that our expression agrees with $F_n$ when $n = 0$ and when $n = 1$. The only thing we must show then is that our expression agrees with $F_{n+1} = F_n + F_{n-1}$. That is, we have to show that $\dfrac{\varphi^{n+1} - \psi^{n+1}}{\sqrt{5}} = \dfrac{\varphi^n - \psi^n}{\sqrt{5}} + \dfrac{\varphi^{n-1} - \psi^{n-1}}{\sqrt{5}}$.

To do this, we can first clear denominators so that what we need to prove is $\varphi^{n+1} - \psi^{n+1} = \varphi^n - \psi^n + \varphi^{n-1} - \psi^{n-1}$.

If we move all the $\varphi$‘s to one side and all the $\psi$‘s to the other, then this equation becomes $\varphi^{n+1} - \varphi^n - \varphi^{n-1} = \psi^{n+1} - \psi^n - \psi^{n-1}$.

We can take out common factors on both sides and arrive at the equation $\varphi^{n-1}(\varphi^2 - \varphi - 1) = \psi^{n-1}(\psi^2 - \psi - 1)$.

Remember that by definition, $\varphi, \psi$ are the two roots of the equation $x^2 - x - 1 = 0$. Therefore, both the left-hand and right-hand sides of the above equation are 0. This shows that our new equation satisfies the third rule, and therefore is identical to the Fibonacci sequence.

We now want to ask about our approximate formula $F_n \approx \dfrac{\varphi^n}{\sqrt{5}}$. In order for this approximation to round to $F_n$, the difference between the two must be less than one half. That is, the inequality $\bigg| F_n - \dfrac{\varphi^n}{\sqrt{5}} \bigg| < \dfrac{1}{2}$ must be true. The exact formula we just found tells us that $F_n - \dfrac{\varphi^n}{\sqrt{5}} = \dfrac{-\psi^n}{\sqrt{5}}$, and we therefore must show that the inequality $\bigg| \dfrac{\psi^n}{\sqrt{5}} \bigg| < \dfrac{1}{2}$ is true. To see why this is true, remember that earlier we found the identity $\psi = \dfrac{-1}{\varphi}$, and so we also know that $\psi^n = \dfrac{(-1)^n}{\varphi^n}$. Therefore, $\bigg| \dfrac{\psi^n}{\sqrt{5}} \bigg| = \bigg| \dfrac{1}{\varphi^n \sqrt{5}} \bigg|$. Since $\varphi > 1$, $\bigg| \dfrac{1}{\varphi^n} \bigg| < 1$, and since $\sqrt{5} > 2$, $\dfrac{1}{\sqrt{5}} < \dfrac{1}{2}$. Therefore, $\bigg| \dfrac{1}{\varphi^n \sqrt{5}} \bigg| < 1 \cdot \dfrac{1}{2} = \dfrac{1}{2}$.

We can then conclude that the formula $\dfrac{\varphi^n}{\sqrt{5}}$ will always give the Fibonacci number $F_n$ when rounded to the nearest whole number. This completes our search for the exact formula for $F_n$.

In the posts that follow, we will show how we can find even more patterns in the Fibonacci numbers using some of these observations, and how we can use the same observations to find formulas to sequences that are similar to the Fibonacci sequence.