Some friends, one of whom is a high school student, asked me to explain the phenomenon that the ratio of successive Fibonacci numbers tends toward the golden ratio. Some of the explanations I have seen involve fairly heavy use of linear algebra; others involve generating functions and the use of some analysis. I wanted to give an explanation that I would have had a prayer of understanding when I was a high school student. I’m not sure whether I have succeeded—there are a great many things I found hard to understand as a high school student (and now as well)—so I would be happy to hear about alternatives or other suggestions. As I see it, there are five main steps in the reasoning. This proof is the one in the Wikipedia article on the Fibonacci numbers, but I have expanded the explanation quite a bit. I highly recommend Peter Cameron’s series of posts about the Fibonacci numbers (see I, II, III, IV, V, and VI). Part 3 of that series is closely related to the topic of this post, but at a somewhat higher level.
Step 1: As is often the case in mathematics, in order to understand a phenomenon, it is helpful to consider a more general phenomenon. The sequence of Fibonacci numbers is just one of infinitely many “Fibonacci-like” sequences that obey the Fibonacci rule . The Fibonacci numbers themselves are generated under the assumptions but if you choose and to be any other random numbers that you like, and then apply the Fibonacci rule to generate and so on, you get another Fibonacci-like sequence.
An example of such a sequence is the Lucas numbers, which are generated from the starting pair . The resulting sequence is
You can try generating some random Fibonacci-like sequences, and you will find, unless you are extremely unlucky (or perhaps I should say lucky), that the ratio of successive terms tends toward the golden ratio, just as ratios of Fibonacci numbers themselves do. What I mean by “extremely unlucky” is that there do exist choices of starting pair for which you get a ratio different from the golden ratio, but these choices are very rare, and you are unlikely to pick one of them by chance.
Step 2: If you multiply every number in a Fibonacci-like sequence by the same value, the resulting sequence is also Fibonacci-like. For example, if you multiply every Fibonacci number by 5, you get the sequence which is Fibonacci-like since it obeys the Fibonacci rule, . Furthermore, if you add two Fibonacci-like sequences together, term-by-term, the resulting sequence is Fibonacci-like. For example, adding the Fibonacci and Lucas sequences gives
which is Fibonacci-like.
Make sure you understand why both of these facts are true. You can, of course, combine the two operations together. For example, you could multiply the Fibonacci numbers by 5 and the Lucas numbers by 12, and then add the resulting sequences term-by-term, and the result will be another Fibonacci-like sequence. In this example you would get
Step 3: Any Fibonacci-like sequence can be expressed as a combination of the Fibonacci sequence and the Lucas sequence. If we let be the Fibonacci sequence and we let be the Lucas sequence, then any other Fibonacci-like sequence equals for some suitable choice of the numbers and
For example, consider the Fibonacci-like sequence with starting pair 4, 9. The sequence this pair produces is How can we express this in terms of Fibonacci and Lucas sequences as The sequence is and the sequence is The sequence is therefore To find and we require that the terms in this sequence match our sequence So we have to solve the simultaneous linear equations
In fact, we can ignore all the equations from the third on, since if the first two equations are satisfied, all the higher ones will automatically hold. (Make sure you understand why.) So we carry out the algebra to find the and that will make the first two equations hold true. You should try this. The answer is You can then verify that if you multiply the Fibonacci numbers by 14, multiply the Lucas numbers by −5, and add the resulting sequences term-by-term, you do indeed get our sequence
Since the same algebraic procedure can be carried out for any Fibonacci-like sequence whatsoever, any Fibonacci-like sequence is a combination of the Fibonacci and Lucas sequences.
There is nothing sacred about using the Fibonacci and Lucas numbers as a basis, however. Any two Fibonacci-like sequences—as long as they are not multiples of each other—can be used as a basis for all other Fibonacci-like sequences. So if and are Fibonacci-like sequences, and is not simply equal to for some number then any Fibonacci-like sequence can be written as
Step 4: To understand why the ratio of successive terms in a Fibonacci-like sequence (usually) tends toward the golden ratio, I will choose the basis sequences and in a very special way. Since we are interested in ratios of successive terms in Fibonacci-like sequences, we ask ourselves, is there a Fibonacci-like sequence for which the ratio of successive terms doesn’t merely tend toward some fixed ratio, but exactly equals the same ratio for all pairs of successive terms in the sequence?
A sequence in which the ratio of successive terms is always the same is called a geometric sequence. If the initial term is and the ratio between successive terms is then the geometric sequence is For example, if the intial term is and the ratio between successive terms is , then the geometric sequence is
Could a Fibonacci-like sequence be a geometric sequence? For this to be the case, we need for the Fibonacci rule, to hold for the terms of the geometric sequence. This means that a system of simultaneous equations must be satisfied:
If the first of these equations holds, then all the others do to, since they are obtained by multiplying both sides of the first equation by or or or a higher power of
So can we find a ratio such that We can get rid of the factor of so we need to solve or The quadratic formula gives two solutions which we will call and
You will recognize as the golden ratio. Since and are the roots of you can write
from which you can conclude that and You can also check these directly, the second one by writing and then rationalizing the denominator.
What this means is that for a Fibonacci-like sequence to be a geometric sequence, the ratio between successive terms has to be either or Choosing the initial term to be 1, the two geometric, Fibonacci-like sequences are
Of course, neither if these is the Fibonacci or Lucas sequence, or any other familiar sequence. The numbers in these sequences are not whole numbers, after all. Rounded to three decimal places, these sequences are
Among all Fibonacci-like sequences, these two sequences are very special: they are geometric. If you multiply either of them by a number, the resulting sequence will still be geometric. But as soon as you start forming other combinations, by adding sequences together, the result will no longer be geometric (although, as discussed in Step 2, it will remain Fibonacci-like).
Step 5: Just as in Step 3, where we expressed Fibonacci-like sequences using the Fibonacci and Lucas sequences as a basis, we can express any Fibonacci-like sequence using the geometric sequences and as a basis, that is, we can write any Fibonacci-like sequence as
As an example, let’s try to express the Lucas sequence in terms of and We need to find numbers and so that
So we need to solve the simultaneous equations
I’ll leave it for you to carry out the algebra, but you should find that This means that the nth Lucas number, which we call equals (Verify this. You should find that and so on.) This is a remarkable formula. The Lucas numbers are whole numbers, whereas and are irrational numbers. The formula says that if you add the nth powers of and together, you always get a whole number.
Now here’s the important point. The nth power of is huge once reaches appreciable size. This is because is a number bigger than 1, and so grows exponentially. On the other hand, the nth power of is tiny since is smaller than 1 in magnitude, which means that decays exponentially. Since is a whole number, but is tiny, we see that will be very close to a whole number once reaches appreciable size.
In other words, although the powers of the golden ratio are irrational numbers, these powers will be very nearly whole numbers once the power gets large. Since the tiny term is alternately positive and negative, the dominant term will be alternately smaller than and bigger than the whole number it approximates.
At last the Fibonacci numbers! We will write the sequence of Fibonacci numbers using the geometric sequences and as a basis. The algebra is similar to the algebra for the Lucas sequence. We require
If you solve for and and rationalize the denominators you should find that
You can also divide numerators and denominators by and you will find that
Hence the nth Fibonacci number, which we call can be written as
Let’s now compute the ratio of the nth and (n−1)st Fibonacci numbers:
Observe that is smaller than 1 in magnitude, so is tiny when gets large. Hence the ratio of successive Fibonacci numbers, which equals times a fraction whose numerator and denominator both get closer and closer to 1 as gets large, approaches as gets large.
Some final remarks. I said that, with some rare exceptions, the ratio of successive terms in any Fibonacci-like sequence—call it —will be close to Let me explain this. Using the sequences and as a basis, so that our sequence is expressed as for some numbers and we see that the nth term in our Fibonacci-like sequence is Take the ratio of the (n+1)st and nth terms:
If is not zero, then numerator and denominator can be divided by to give
which tends to as gets large, since becomes tiny. On the other hand, if is zero, we cannot divide numerator and denominator by In fact, the ratio is simply rather than So this is the special case where the limiting ratio is not the golden ratio. In this situation, the limiting ratio instead is −1 divided by the golden ratio.
We could say that any Fibonacci-like sequence is a mixture of the sequence of powers of and the sequence of powers of If there is no in the mixture, then the ratio of successive terms is simply If there is no in the mixture, then the ratio of successive terms is simply If the mixture contains both and then since gets huge while gets tiny, the contribution can be ignored for large, and so the ratio of successive terms tends toward An “unlucky choice” of initial terms would be or more generally which would generate a Fibonacci-like sequence that is a multiple of and therefore contains no in the mixture.
If you have read this far, you may have noticed that linear algebra did make an appearance after all. The use of the word “basis” is a clue that the idea of a vector space is lurking. More specifically, the Fibonacci-like sequences form a two-dimensional vector space. The focus on Fibonacci-like sequences that are also geometric sequences is a way of sneaking in the matrix diagonalization proof described in Peter Cameron’s third post.