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 F(n) = F(n-1) + F(n-2).  The Fibonacci numbers themselves are generated under the assumptions F(0) = 1, F(1) =1, but if you choose F(0) and F(1) to be any other random numbers that you like, and then apply the Fibonacci rule to generate F(2), F(3), 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 F(0) = 2, F(1) = 1.  The resulting sequence is 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, \ldots
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 5, 5, 10, 15, 25, 40, 65, 105, \ldots, which is Fibonacci-like since it obeys the Fibonacci rule, F(n) = F(n-1) + F(n-2).  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

(1+2, 1+1, 2+3, 3+4, 5+7, 8+11, 13+18, 21+29, \ldots) = (3, 2, 5, 7, 12, 19, 31, 50, \ldots),

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 (29, 17, 46, 63, 109, \ldots).
Step 3: Any Fibonacci-like sequence can be expressed as a combination of the Fibonacci sequence and the Lucas sequence.  If we let f = (1, 1, 2, 3, 5, 8, 13, 21, \ldots) be the Fibonacci sequence and we let \ell = (2, 1, 3, 4, 7, 11, 18, 29, \ldots) be the Lucas sequence, then any other Fibonacci-like sequence equals x\cdot f + y\cdot\ell for some suitable choice of the numbers x and y.
For example, consider the Fibonacci-like sequence with starting pair 4, 9.  The sequence this pair produces is (4, 9, 13, 22, 35, 57, 92, \ldots).  How can we express this in terms of Fibonacci and Lucas sequences as x\cdot f + y\cdot\ell?  The sequence x\cdot f is (x, x, 2x, 3x, 5x, 8x, 13x, \ldots) and the sequence y\cdot\ell is (2y, y, 3y, 4y, 7y, 11y, 18y, \ldots).  The sequence x\cdot f + y\cdot\ell is therefore (x+2y, x+y, 2x+3y, 3x+4y, 5x+7y, \ldots).  To find x and y, we require that the terms in this sequence match our sequence (4, 9, 13, 22, 35, \ldots).  So we have to solve the simultaneous linear equations

\begin{aligned}x+2y&=4,\\ x+y&=9,\\ 2x+3y&=13,\\ 3x+4y&=22,\\ &\vdots\end{aligned}

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 x and y that will make the first two equations hold true.  You should try this.  The answer is x = 14, y = -5.  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 (4, 9, 13, 22, 35, \ldots).
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 A and B are Fibonacci-like sequences, and B is not simply equal to c\cdot A for some number c, then any Fibonacci-like sequence can be written as x\cdot A + y\cdot B.

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 A and B 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 a and the ratio between successive terms is r, then the geometric sequence is (a, ar, ar^2, ar^3, ar^4, \ldots).  For example, if the intial term is a=3 and the ratio between successive terms is r=2, then the geometric sequence is (3, 6, 12, 24, 48, 96, \ldots).

Could a Fibonacci-like sequence be a geometric sequence?  For this to be the case, we need for the Fibonacci rule, F(n) = F(n-1) +F(n-2), to hold for the terms of the geometric sequence.  This means that a system of simultaneous equations must be satisfied:

\begin{aligned} ar^2&=ar+a,\\ ar^3&=ar^2+ar,\\ ar^4&=ar^3+ar^2,\\ &\vdots\end{aligned}

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 r or r^2 or r^3 or a higher power of r.
So can we find a ratio r such that ar^2 = ar + a?  We can get rid of the factor of a, so we need to solve r^2 = r + 1, or r^2 - r - 1 = 0.  The quadratic formula gives two solutions which we will call \phi and \psi:

\begin{aligned}\phi&=\frac{1 + \sqrt{5}}{2},\\ \psi&=\frac{1 - \sqrt{5}}{2}.\end{aligned}

You will recognize \phi as the golden ratio.  Since \phi and \psi are the roots of r^2 - r - 1, you can write

r^2 -r - 1 = (r - \phi)(r - \psi)=r^2-(\phi+\psi)r+\phi\psi,

from which you can conclude that \phi+\psi=1 and \psi = -1 / \phi.  You can also check these directly, the second one by writing -1 / \phi = -2 / (1 + \sqrt{5}) 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 \phi or \psi.  Choosing the initial term to be 1, the two geometric, Fibonacci-like sequences are

\begin{aligned}A &= (1, \phi, \phi^2, \phi^3, \phi^4, \ldots),\\ B &= (1, \psi, \psi^2, \psi^3, \psi^4, \ldots).\end{aligned}

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

\begin{aligned}A &=(1, 1.618, 2.618, 4.236, 6.854, 11.090, 17.944, 29.034, 46.979, 76.013, 122.992, \ldots),\\ B &= (1, -0.618, 0.382, -0.236, 0.146, -0.090, 0.056, -0.034, 0.021, -0.013, 0.008, \ldots).\end{aligned}

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 A and B as a basis, that is, we can write any Fibonacci-like sequence as x\cdot A + y\cdot B.

As an example, let’s try to express the Lucas sequence in terms of A and B.  We need to find numbers x and y so that

x\cdot A + y\cdot B = (2, 1, 3, 4, 7, 11, 18, 29, \ldots).

So we need to solve the simultaneous equations

\begin{aligned}x + y &= 2\\ x \phi + y \psi &= 1.\end{aligned}

I’ll leave it for you to carry out the algebra, but you should find that x = 1, y = 1.  This means that the nth Lucas number, which we call \ell(n), equals \phi^n + \psi^n.  (Verify this.  You should find that \ell(0) = 2, \ell(1) = 1, \ell(2) = 3, and so on.)  This is a remarkable formula.  The Lucas numbers are whole numbers, whereas \phi and \psi are irrational numbers.  The formula says that if you add the nth powers of \phi and \psi together, you always get a whole number.
Now here’s the important point.  The nth power of \phi is huge once n reaches  appreciable size.  This is because \phi = 1.618\ldots is a number bigger than 1, and so \phi^n grows exponentially.  On the other hand, the nth power of \psi is tiny since \psi = -0.618\ldots is smaller than 1 in magnitude, which means that \psi^n decays exponentially.  Since \phi^n + \psi^n is a whole number, but \psi^n is tiny, we see that \phi^n will be very close to a whole number once n 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 \psi^n is alternately positive and negative, the dominant term \phi^n 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 A and B as a basis.  The algebra is similar to the algebra for the Lucas sequence.  We require

\begin{aligned}x + y &= 1,\\ x \phi + y \psi &= 1.\end{aligned}

If you solve for x and y and rationalize the denominators you should find that

\displaystyle x = \frac{5 + \sqrt{5}}{10}\quad\text{ and }\quad y =\frac{5 - \sqrt{5}}{10}.

You can also divide numerators and denominators by \sqrt{5}, and you will find that

\displaystyle x = \frac{\sqrt{5} + 1}{2\sqrt{5}} = \frac{\phi}{\sqrt{5}}\quad\text{ and }\quad y = \frac{\sqrt{5} - 1}{2\sqrt{5}} = \frac{-\psi}{\sqrt{5}}.

Hence the nth Fibonacci number, which we call f(n), can be written as

\displaystyle f(n)=\frac{\phi^{n+1} - \psi^{n+1}}{\sqrt{5}}.

Let’s now compute the ratio of the nth and (n−1)st Fibonacci numbers:

\begin{aligned}\frac{f(n)}{f(n-1)} &= \frac{(\phi^{n+1} - \psi^{n+1}) / \sqrt{5}}{(\phi^n - \psi^n) / \sqrt{5}} = \frac{\phi^{n+1} - \psi^{n+1}}{\phi^n - \psi^n}\\ &= \frac{\phi - \psi^{n+1}/\phi^n}{1 - \psi^n/\phi^n} = \phi\,\frac{1 - (\psi/\phi)^{n+1}}{1 - (\psi/\phi)^n}.\end{aligned}

Observe that \psi / \phi is smaller than 1 in magnitude, so (\psi / \phi)^n is tiny when n gets large.  Hence the ratio of successive Fibonacci numbers, which equals \phi times a fraction whose numerator and denominator both get closer and closer to 1 as n gets large,  approaches \phi as n gets large.

Some final remarks.  I said that, with some rare exceptions, the ratio of successive terms in any Fibonacci-like sequence—call it g—will be close to \phi.  Let me explain this.  Using the sequences A and B as a basis, so that our sequence is expressed as g=x\cdot A + y\cdot B for some numbers x and y, we see that the nth term in our Fibonacci-like sequence g is g(n)=x \phi^n + y \psi^n.  Take the ratio of the (n+1)st and nth terms:

\displaystyle \frac{g(n+1)}{g(n)} = \frac{x \phi^{n+1} + y \psi^{n+1}}{x \phi^n + y \psi^n} = \phi\,\frac{x + y (\psi/\phi)^{n+1}}{x + y(\psi/\phi)^n}.

If x is not zero, then numerator and denominator can be divided by x to give

\displaystyle\phi\,\frac{1 + \frac{y}{x} \left(\frac{\psi}{\phi}\right)^{n+1}}{1 + \frac{y}{x} \left(\frac{\psi}{\phi}\right)^n},

which tends to \phi as n gets large, since (\psi/\phi)^n becomes tiny.  On the other hand, if x is zero, we cannot divide numerator and denominator by x.  In fact, the ratio g(n+1)/g(n) is simply \psi rather than \phi.  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 A of powers of \phi and the sequence B of powers of \psi.  If there is no A in the mixture, then the ratio of successive terms is simply \psi.  If there is no B in the mixture, then the ratio of successive terms is simply \phi.  If the mixture contains both A and B, then since \phi^n gets huge while \psi^n gets tiny, the B contribution can be ignored for n large, and so the ratio of successive terms tends toward \phi.  An “unlucky choice” of initial terms would be 1, \psi, or more generally a, a \psi, which would generate a Fibonacci-like sequence that is a multiple of B, and therefore contains no A 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.

About these ads