|GBB Services : Resources : Mathematics : Fibonacci numbers|
The Fibonacci Numbers Revisited
The recursive definition
A combinatorial characterization
Another combinatorial characterization
A picture sometimes helps
A generating function
The geometric sequence
Relevance of the geometric sequence
Projection of a two dimensional geometric sequence
Discovering Binet's formula
Using inner products to get a result
The Fibonacci numbers are
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
They're usually denoted F0, F1, F2, F3, F4, … and each term is the sum of the previous two terms (except for the first two, which are just given as 0 and 1).
If you've ever studied this series, you probably know that there's a multitude of relationships and theorems involving the Fibonacci numbers. They're usually proved by induction, building on the inductive definition of the Fibonacci series. Unfortunately, proofs by induction usually provide very little insight.
Fortunately, there are several alternative ways to describe the series, some of which give a different insight into why certain facts involving these numbers are true. That's the subject of this essay.
Until very recently, I knew of only four ways to describe the numbers: the usual recursive way, the analytical formula involving powers of the golden ratio and its negative reciprocal (Binet's formula), a combinatorial characterization, and via a generating function. I recently realized that there's yet another way to describe the Fibonacci sequence, as a projection of a two dimensional geometric sequence, and that prompted me to write this essay. As I began writing, I also realized that revisiting the Fibonacci numbers after learning about vector spaces, linear algebra, eigenvalues, symmetric matrices and inner products also helps clear things up. I'll write about that also.
The starting values of 0 and 1 are kind of arbitrary, and mathematicians have studied what happens with other starting constants.
The most famous Fibonacci like numbers are the Lucas numbers, which use the Fibonacci recurrence relationship, but start with 2 and 1. They are
2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, …
They're usually denoted L0, L1, L2, L3, L4,…
Finally, given constants G0 and G1, the resulting Generalized Fibonacci sequence generated by the Fibonacci recurrence relationship is usually denoted G0, G1, G2, G3, G4,… Of course, G0=0, G1=1 gives the standard Fibonacci sequence, while G0=2, G1=1 gives the Lucas sequence.
Incidentally, Lucas numbers are named after the French mathematician Edouard Lucas, who is also the inventor of the Towers of Hanoi puzzle. I learned this from my favorite popular mathematics author, David Wells, in his book "Prime Numbers". I strongly recommend reading any of his books.
Finally, I should explicitly mention that one of the many reasons to consider these variations on the Fibonacci numbers is to give us insight into theorems about the Fibonacci numbers. Finding out if there is a Lucas number analogue of a Fibonacci number theorem might help us understand the Fibonacci version. And, of course, if a generalization involving the Generalized Fibonacci sequence can be found, that helps us understand which properties of the Fibonacci sequence are relevant and which aren't.
F0 = 0
F1 = 1
The golden ratio φ is (1+√5)/2. It's a famous constant that was identified more than a thousand years before Fibonacci defined the Fibonacci numbers.
It's defined to be the positive root of the quadratic equation x = 1/(x-1), ie x2 - x - 1 =0. The other root is a negative number with absolute value smaller that 1, namely -1/φ. This is sometimes called the golden ratio conjugate, and is equal to (1-φ).
There are many links between the golden ratio and the Fibonacci numbers. One of them is Binet's formula for the Fibonacci numbers:
The corresponding formula for Lucas numbers is
For a Generalized Fibonacci sequence,it's always possible to find constants a and b for which
One way to see that this is true is described later in this essay.
Note that since
we have that
This is not so clear via the inductive definition.
Another immediate consequence of these formulas for the Fibonacci and Lucas sequences is the relationsip
It follows from the algebraic identity (x-y)(x+y) = x2-y2 as follows:
FnLn=((φn − (1-φ)n ) / √5) (φn + (1-φ)n)= (φ2n − (1-φ)2n ) / √5 = F2n
There's a combinatorial description involving strings of two characters (call them 'A' and 'B', to be specific). The nth Fibonacci number is the number of (A,B) strings of length n-2 that don't contain any consecutive B's.
For example, to compute F6, find all the strings of length 4 (since 6-2=4) that don't have consecutive B's. They are
AAAA, AAAB, AABA, ABAA, ABAB, BAAA, BAAB, BABA.
There's 8 of them, and so F6 is 8, as expected.
This characterization is occasionally useful in giving insight into the behavior of the Fibonacci series that the other descriptions don't.
For example, you might amuse yourself, as I did many years ago, by proving the identity
Fn2 + Fn+12 = F2n+1
using the different characterizations.
The recursive characterization will give you a proof by induction, and the analytical characterization will give you a proof by algebraic manipulation. Both are valid proofs, but don't give any insight into how the result could ever be found in the first place.
The combinatorial characterization gives a proof that could have actually been used to find the identity, even if you didn't know ahead of time that the identity existed. The proof involves counting the number of strings of length 2n-1 (we know that there are F2n+1 of them) as the sum of the number of strings that have middle character "A" (there are Fn+12 of them) and the number of strings that have middle character "B" (there are Fn2 of them). It can also be used to derive an unlimited number of similar results like
Fn+1F2n+1 + Fn+2F2n+2 = F3n+3 .
There's also a combinatorial description involving ways of summing ones and twos. The nth Fibonacci number is the number of sequences of ones and twos with sum n-1.
For example, to compute F6, find all the sequences of ones and twos that add up to 5 (since 6-1=5). They are
11111, 1112, 1121, 1211, 122, 2111, 212, 221.
There's 8 of them, and so F6 is 8, as expected.
This characterization can be useful when relating results about the Fibonacci numbers and the binomial coefficients (aka the numbers in Pascal's triangle).
One example is the result
This is just saying that the number of sequences of ones and twos that add up to n is equal to the number of such sequences with zero twos, plus the number with one two, plus the number with two twos, plus the number with three twos, etc.
I'm not going to write much more about this since a whole book has recently been written on understanding Fibonacci numbers (and Lucas numbers and Generalized Fibonacci numbers) in terms of combinatorial characterizations like these. It's "Proofs that Really Count" (2003) by Arthur Benjamin and Jennifer Quinn. I recommend browsing through it, despite the fact that the authors insist on referring to Generalized Fibonacci numbers as Gibonacci numbers.
Sometimes a picture helps. For example, drawing a picture makes it clear that the sequence with nth term
must satisfy the Fibonacci recurrence. Here's the picture:
Of course, you still need to check the base cases to make sure you're dealing with the Fibonacci sequence.
A nice little result involving sums of squares of Fibonacci numbers is
There's a generalization involving Generalized Fibonacci numbers:
If you like this kind of thing, you might like reading my essay Table Proofs.
A generating function f for the infinite sequence
The generating function for the Fibonacci sequence is x / (1 - x - x2).
This is nice to know, and has led to the discovery of new identities, but it hasn't helped me understand anything about the Fibonacci numbers. The only use I've ever found for this generating function is to entertain people who have infinite precision calculators. One of many examples is:1000/998999 = 0 .001 001 002 003 005 008 013 021 03405508914423337761098859958818777596374
One of the many identities discovered by using the generating function is Binet's formula. That's how De Moivre found the formula. The idea is to first use a partial fraction decomposition, then expand the two terms into two infinite geometric series, and then collect similar terms. Details can be found in John Stillwell's "Mathematics and Its History" or in Donald Knuth's "The Art of Computer Programming Volume 1" .
A geometric sequence x0, x1… is one in which the first term x0 is arbitrary, usually denoted by "a", and the ratio of terms xn/xn-1 is a constant, usually denoted by "r". iexn = r xn-1
x0 = a
Equivalently, in terms of powers,xn = a rn
Probably the best known special case is the doubling sequence 1, 2, 4, 8, 16, 32, 64 … It's given by a=1 and r=2. I vividly remember computing out to the 20th term and beyond when I was seven. Strangely enough, many mathematicians I've talked with report a similar story of their own. There's something about doubling that's very captivating.
Geometric sequences are very well known and reasonably straightforward to work with. Some of the results you might have encountered are
x0 + x1 + x2 + x3 + … + xn = (xn+1 - x0) / (r - 1)
This follows from realizing that rSn - Sn = arn+1 - a , for
One possible way to discover this for yourself is by playing around with the sum Sn and noticing that rSn has almost exactly the same terms as Sn. Once you realize that, taking their difference to get a simple expression is hard to avoid (he says with the benefit of hindsight).
The usual way to connect up geometric sequences and Fibonacci sequences (I first learned it in a probability class as an undergraduate) is to find out which geometric sequences are also Generalized Fibonacci sequences. Assuming that Gn = arn and substituting into the recurrence Gn = Gn-1 + Gn-2, we getarn = arn-1 + arn-2.
This immediately simplifies to the quadratic equation for the golden ratior2 = r + 1
So, the geometric sequences that are also Generalized Fibonacci sequences are the ones for which r = φ or (1-φ).
Since linear combinations of Generalized Fibonacci sequences are also Generalized Fibonacci sequences, it follows that sequences whose nth term isa φn + b (1-φ)n
are Generalized Fibonacci sequences. Furthermore, via elementary linear algebra, these sequences are precisely the Generalized Fibonacci sequences. One way to prove it is to show that both sets of sequences form a two dimensional vector space, and if one is contained in the other, they must be equal.
For those of you who might want a little more detail, here it is. The space of Generalized Fibonacci sequences is a vector space since it's a subspace of the vector space of sequences. It's two dimensional, since a basis is given by one sequence with (G0,G1)=(1,0) and another with (G0,G1)=(0,1) (ie the Fibonacci sequence). Incidentally, another basis is given by the Fibonacci sequence and the Lucas sequence. Two non zero geometric series with different ratios cannot be multiples of each other, so that means that the geometric sequence with a=1, r=φ, and the geometric sequence with a=1, r=(1-φ) are linearly independent. Since the subspace generated by n linearly independent elements of an n dimensional vector space must be the entire vector space, we're done. QED!
The linear recurrence
can be rewritten in matrix form as
It's a standard trick (I've seen it in many contexts, one of which is ordinary differential equations) to rewrite this kind of equation as
This is of course the same as
where Xn (a sequence of two dimensional points) and F (a linear transformation) are given by
Xn = F Xn-1 should look familiar: it's the recurrence equation for a geometric series.
Just like before, we have Xn = Fn X0. There are analogues of results for the one dimensional geometric sequence in the two dimensional case. One example is that Sn, the sum of terms from X0 to Xn is given by pretty much the same formula as before
Finally, to recover the Fibonacci sequence from the two dimensional geometric sequence, just grab the second entry, ie project the points onto the y axis.
To be painfully explicit, the projection operator that takes two dimensional points and sends them to the y axis is
In terms of this operator, we can write
This kind of thing happens in many places in mathematics (and related fields such as physics).
An example I really like is the identity for sine of a sum. It's clear, in the context of two dimensional space, that a rotation by angle α followed by a rotation of angle β gives a rotation by angle α+β. Applying this to the unit x vector, we get the identity
Projecting to the y axis, we get the well known identity
It seems to me that it really helps to understand the above one dimensional identity by viewing it as the projection of a two dimensional identity. Also, in case you're wondering, projecting onto the x axis instead of the y axis gives a corresponding identity for cos(α+β).
Sticking with this a little more, the trigonometric sine function is really the projection onto the y axis of the function describing uniform motion around a circle: if you view a helix from the side, you'll see a sine curve.
Yet another example is from general relativity. The motion path of a particle in 3d space is really the projection from 4d space-time of a geodesic. The familiar parabola described by a thrown object (which is really the tip of a very thin ellipse) turns out to be the projection of a space-time geodesic.
What we want is results about two dimensional geometric sequences that are "natural" or easy to discover, but whose projection to the one dimensional y axis leads to results (about Fibonacci numbers) that are mysterious or puzzling.
The first candidate is the summation formulaG0 + G1 + … + Gn = Gn+2 - G1
As mentioned above, the sum of a geometric series is given byX0 + X1 + … + Xn = ( F - I )-1 (Xn+1 - X0)
Since F satisfies the golden ratio quadratic ie F2 = F + I, we have F = (F - I)-1, and soX0 + X1 + … + Xn = F (Xn+1 - X0) = Xn+2 - X1
The projection of this to the y axisPy(X0 + X1 + … + Xn) = Py(Xn+2 - X1)
is the summation result for the Generalized Fibonacci sequenceG0 + G1 + … + Gn = Gn+2 - G1
The second candidate is the efficient computation of the Fibonacci numbers. A naive approach is to use the linear time iterative approach: use F0 and F1 to get F2, then use F1 and F2 to get F3 and so on until we get Fn. In fact, there's a logarithmic time algorithm, and it's just the projection of the logarithmic time algorithm for computing the nth term of a geometric sequence, namely repeated squaring.
In case you haven't seen this before, here are more details: rn, for n greater than 1, can be computed as (rn/2)2 for n even, and (r)(rn-1) for n odd. Recursing down to n=1, it follows that 2 log2(n) multiplications are enough to compute rn.
As I showed above, once you think to look for the one dimensional geometric sequences that happen to be Generalized Fibonacci sequences, you're inevitably led to the Binet formula. But, it's unclear how anyone would ever find this approach to Binet's formula. Fortunately, there is an alternative approach that is completely natural, in my opinion.
The instant any mathematician sees the matrix F, he'll notice that it's symmetric, and so Euler's principal axes theorem holds. This means that the matrix must have two real eigenvalues, and the corresponding eigenvectors are orthogonal. Finding the eigenvectors and eigenvalues of a symmetric matrix are essential first steps to understanding anything involving the matrix, since they reveal the behavior of the linear transformation, independent of coordinate choices.
The eigenvalue equation for F is the golden ratio equation. This means that the eigenvalues are φ (the golden ratio) and (1-φ).
Writing v and w for the corresponding eigenvectors, so that F v = φ v and F w = (1-φ) w, we have
for all scalars a and b.
Writing X0 as a linear combination (a v + b w) of v and w, and using the fact that Xn = Fn X0, we have
Projecting to the y axis, we get
In other words, there are constants A and B for which
From here, getting Binet's formula for the Fibonacci numbers is a "no brainer".
A little searching on the internet reveals that Binet published the formula named after him in 1843, but Euler had published the result way back in the 1700's. I haven't yet found that publication, and I still don't know how Euler derived the result. It could be that the above derivation is how Euler found the result. He certainly knew about Euler's principal axes theorem. [ * ]
The fact that the matrix F is symmetric immediately tells a mathematician that the transformation is self adjoint. In other words, for any two vectors v and w, we have
where < v , w > is the usual Euclidean inner product.
It follows immediately that
This is just the Generalized Fibonacci identity
The special case for the Fibonacci numbers is of course
You might remember that we saw the case where m=n ( ie F2n+1 = Fn+12 + Fn2 ) in the combinatorial section
Incidentally, a more symmetric way of expressing the general identity is
whenever a+b = m+n.
Just to be sure I hadn't missed anything obvious, I looked at the wikipedia article on Fibonacci numbers, and the only significant element I seem to be missing is a discussion of continued fractions, and their connection to Fibonacci numbers and the golden ratio. Also, I never mentioned that
I couldn't find a natural way to work it in. I'll refer you to the wikipedia page if you want to learn more.
[ 1 ] John Stillwell was kind enough to send me some feedback on the original discovery of the Binet formula, and it turns out that none of the people who (probably) independently discovered Binet's result (Daniel Bernoulli, de Moivre, and Euler) used eigenvectors of the Fibonacci matrix to get Binet's formula.Euler's publication, from 1765, is in the Euler archive as paper E326. It's written in latin, but John points out that there's an English commentary.
Also, I should mention that I strongly recommend reading John's many books. I've enjoyed learning from him for decades, ever since I had the pleasure to take some of his classes as an undergraduate. De Moivre's method for discovering the Binet formula is included in his book "Mathematics and Its History".
[ 2 ] Alex Stepanov has suggested that I mention another reference: Thomas Koshy's "Fibonacci and Lucas Numbers with Applications". He writes that "It is a treasure trove of Fibonacci numbers lore accessible to a high school student". This book somehow slipped through the cracks for me, and I didn't notice it when it came out in 2001. I hope to get my hands on it soon.
Finally, I should mention that Alex deals with the the Fibonacci numbers and the Fibonacci matrix in the context of programming in his upcoming book "Elements of Programming" (in Chapter 2 "Algorithms on algebraic structures"). Preliminary drafts can be found at his site http://www.stepanovpapers.com/
[ 3 ] David Angell wrote me an email in which he revealed that "Personally I am quite fond of relations between the Fibonacci numbers and binomial coefficients …". He then told me about the combinatorial characterization involving ones and twos, how it can be used to prove the result about diagonals of Pascal's triangle, and then continued by mentioning "… And (alternative proof) just drawing up the triangle and colouring in two consecutive diagonals makes it beautifully obvious how they fit together and satisfy the Fibonacci recurrence.". I've added several sections to this essay to include these results. Thank you David!
David lectures in the the School of Mathematics at the University of New South Wales in Australia. If you visit his home page at http://web.maths.unsw.edu.au/~angell , be sure to scroll all the way down, otherwise you won't notice his section on "Extension articles".
If you have corrections, additions, modifications, etc please let me know mailto:email@example.com