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).

Table of values for our first guess

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):

nF_n\varphi^n\varphi^n / F_nF_n - \dfrac{\varphi^n}{2.236}
Adjusted table for our first guess

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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: