# Finding the Fibonacci Numbers: Getting Our Bearings

This is the second in a series of posts discussing a quite elegant and interesting problem in the history of mathematics. We have previously defined the Fibonacci numbers $F_n$ using the starting point $F_0 = 0, F_1 = 1$ and defining $F_{n+1} = F_n+ F_{n-1}$ for every larger value of $n$. This set up is often called a recursive formula, since we use the same process over and over again to obtain ever-larger values in our sequence of numbers. By using this process, we can see that $F_2 = 1 + 0 = 1, F_3 = 1 + 1 = 2, F_4 = 2 + 1 = 3$, and so on. At the end of the first post in this series, we asked a question. We want to know whether there is a formula for $F_n$ that can bypass the requirement of knowing all the previous values of $F_n$. It is not at all obvious what such a formula might look like at the start, but we will fall back on some more intuitive ideas in order to try to find a relationship between these $F_n$ values and other things we know about already.

How Big are the Fibonacci Numbers?

When you study mathematics or science for a long time, there is an overarching principle that you see over and over again that is usually quite helpful for problems like this. Here is the principle – the first step should be to just get close to the right answer, and after that you can try to work out the small errors in your guess. This way of thinking has a significant role in thinking about how rapidly the values you care about are increasing. Different important functions in mathematics increase at different speeds, and so by figuring out the speed of increase, you can figure out the “shape” of the formula you are looking for, so to speak.

To see what I mean, let’s consider a couple different kinds of functions. First, think about lines. The function for a line is $y = mx + b$ for some constants $m,b$. For simplicity, we will use $y = 2x + 1$. When you plug in $x = 0, 1, 2, 3, 4, 5$, you find the $y$-values are $1, 3, 5, 7, 9, 11$. When you look at how quickly the $y$-values increase, you can see that the values go up by 2 every time. What does this mean conceptually? If we look at our $F_n$ sequence and notice that it goes up by approximately the same value every time $n$ goes up by 1, then $F_n$ is going to have a formula that looks similar to the line equation $y = mx + b$.

For our second function, let’s think about quadratic equations, which look like $y = ax^2 + bx + c$ for some constants $a,b,c$. To make this simple, we will look at the formula $y = x^2 + 2x + 1$. If we use values of $x$ from 0 to 5 as before, we find the list of $y$-values is $1, 4, 9, 16, 25, 36$. If we look at the gaps between consecutive numbers, another way of expressing how $y$ is increasing, the gaps (if we start at 0) have sizes $1, 3, 5, 7, 9, 11$. Looking back at the last paragraph, this is the same list that we got for the $y$-values of $y = 2x+1$. What we learn from this is that if the gaps between $F_{n+1}$ and $F_n$ looks something like an equation for a line, then the equation for $F_n$ looks something like $y = ax^2 + bx + c$.

Finally, we will consider a different kind of function – the exponential functions $y = a^x$. For simplicity, we will use $y = 2^x$. We obtain $y$ by multiplying 2 to itself $x$ times (and $2^0 = 1$). Using $x$ values from 0 to 5, the list of $y$-values is $1, 2, 4, 8, 16, 32$. The gaps between consecutive numbers form the list $1, 2, 4, 8, 16$ – the same list! All exponential equations are like this. So, if we look at $F_n$ and we find that the gaps between consecutive numbers look like the original list of $F_n$ values, then the exact formula for $F_n$ should look sort of like $y = a^x$, for some value of $a$.

So, how fast does $F_n$ grow? Well, if we look at the list $1, 1, 2, 3, 5, 8, 13, \dots$, the gaps between consecutive numbers form the list $0, 1, 1, 2, 3, 5 \dots$ – and this is our original list exactly! From our discussion from earlier, we should expect that $F_n$ would be approximately equal to $a^n$ for some constant $a$. We will see later that the correct value for $a$ is a famous number that is usually written with the Greek letter $\varphi$, and so we will use this symbol from here on out.

What Value is ${\bf \varphi}$?

We now want to piece together the actual value of $\varphi$. Is it close to 3? 2? How would we figure that out? We can actually justify this in two ways. We already know that $F_{n+1} = F_n + F_{n-1}$ must be true. It would make sense, then, that if $F_n \approx \varphi^n$ as we have predicted, then the equation $\varphi^{n+1} = \varphi^n + \varphi^{n-1}$ would be true by substituting $\varphi^n$ for every $F_n$. With out new equation, we can actually go ahead and divide out $\varphi$ a total of $n-1$ times, which leaves us with the equation $\varphi^2 = \varphi + 1$. Rearranging this, we now anticipate that $\varphi$ is a solution to the quadratic equation $x^2 - x - 1 = 0$. The quadratic formula tells us that this has two solutions, which are $\dfrac{1 \pm \sqrt{5}}{2}$.

That gives us something to work with. But which one is right? Well, using the $-$ sign gives a negative value, but since $F_n$ is always a positive number, this wouldn’t make sense. So, we should anticipate that $\varphi = \dfrac{1 + \sqrt{5}}{2}$. This number is called the golden ratio, and is well-known for a variety of reasons. The golden ratio appears in art, biology, architecture, and all sorts of places in mathematics and science. You can find almost endless examples of the golden ratio appearing in nature with a quick search on Google or YouTube… and very often, the Fibonacci sequence is connected to these examples too! So this should be an encouraging sign that we are on the right pathway.

But to convince ourselves even more, there is a second way we can arrive at the same solution. Exponential equations like $a^n$ have the nice property that $\dfrac{a^{n+1}}{a^n} = a$ (this is essentially just because multiplication and division cancel each other out). If $F_n \approx \varphi^n$, we should expect that $\dfrac{F_{n+1}}{F_n} \approx \varphi$. This also works out. Since we know that $F_{n+1} = F_n + F_{n-1}$, we can see that

$\dfrac{F_{n+1}}{F_n} = \dfrac{F_n + F_{n-1}}{F_n} = \dfrac{F_n}{F_n} + \dfrac{F_{n-1}}{F_n} = 1 + \dfrac{1}{F_n / F_{n-1}}.$

Remember, since we expect that $F_n$ is basically an exponential function, the fractions $\dfrac{F_{n+1}}{F_n}$ and $\dfrac{F_n}{F_{n-1}}$ should both be approximately $\varphi$. This leaves us with the equation $\varphi = 1 + \dfrac{1}{\varphi}$ – and if we multiply both sides by $\varphi$ we arrive once again at $\varphi^2 = \varphi + 1$. This is the same quadratic we saw earlier, and so we once again conclude that, probably, $F_n \approx \varphi^n$.

How Close Are We Now?

Now that we have a reason to expect that we are close to some kind of formula for $F_n$, we should take a closer look and see how close we actually are. Now I’ll break out a calculator and give a side-by-side comparison of the actual value of $F_n$ and our predicted value $\varphi^n$ (approximated in the table to 3 decimals).

Ok, so the actual numbers themselves seem pretty far off. But to be fair to ourselves, remember that all of our guessing was based on how quickly these things grow, not per se about the actual numbers. Can we find a measure by which we can be a little more confident that we are on the right track? Actually, yes we can. Look at what happens if we add to our table a fourth column (again, rounding to three decimals):

This fourth column seems to level out at the value of 2.236. This means that $\varphi^n / F_n \approx 2.236$, and so $F_n \approx \dfrac{\varphi^n}{2.236}$. The fifth column shows that, in fact, $F_n$ is extremely close to $\dfrac{\varphi^n}{2.236}$. But not exactly equal… which of course is our goal.

We have gone through a lot of work, and it has really paid off. We have now discovered by experimenting with how quickly $F_n$ grows a formula that, to all appearances, seems to incredibly accurate, and in fact accurate enough to give us $F_n$ if we round to the nearest whole number. But our goal here is to find this formula exactly – not just really close. We have two important unanswered questions here.

(1) Where is this 2.236 coming from?

(2) How do we adjust to fix the error in the fifth column?

Take some time and think about these questions yourself. We have already seen ideas that are related to the answers… my hint to my readers is that the answers to both (1) and (2) are closely related to the equation $x^2 - x - 1 = 0$ and the golden ratio $\varphi$. See if you can find any connections, and after you’ve given that a try, move on to the next post, where you can find the complete solution of an exact formula for $F_n$ without any errors – along with a proof that our guess so far actually is correct if we round to the nearest whole number.