GBB Services  
GBB Services : Resources : Mathematics : Fibonacci numbers 
The Fibonacci Numbers Revisitedby Walter VanniniRelated sequences The recursive definition Binet's formula 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 Some context Some consequences Summation identity Efficient computation Discovering Binet's formula Using inner products to get a result Concluding words Feedback IntroductionThe Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … They're usually denoted F_{0}, F_{1}, F_{2}, F_{3}, F_{4}, … 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. Related sequencesThe 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 L_{0}, L_{1}, L_{2}, L_{3}, L_{4},… Finally, given constants G_{0} and G_{1}, the resulting Generalized Fibonacci sequence generated by the Fibonacci recurrence relationship is usually denoted G_{0}, G_{1}, G_{2}, G_{3}, G_{4},… Of course, G_{0}=0, G_{1}=1 gives the standard Fibonacci sequence, while G_{0}=2, G_{1}=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. Binet's formulaThe 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/(x1), ie x^{2}  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 and 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 (xy)(x+y) = x^{2}y^{2} as follows: F_{n}L_{n}=((φ^{n} − (1φ)^{n} ) / √5) (φ^{n} + (1φ)^{n})= (φ^{2n} − (1φ)^{2n} ) / √5 = F_{2n} A combinatorial characterizationThere'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 n2 that don't contain any consecutive B's. For example, to compute F_{6}, find all the strings of length 4 (since 62=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 F_{6} 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 F_{n}^{2} + F_{n+1}^{2} = F_{2n+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 2n1 (we know that there are F_{2n+1} of them) as the sum of the number of strings that have middle character "A" (there are F_{n+1}^{2} of them) and the number of strings that have middle character "B" (there are F_{n}^{2} of them). It can also be used to derive an unlimited number of similar results like F_{n+1}F_{2n+1} + F_{n+2}F_{2n+2} = F_{3n+3} . Another combinatorial characterizationThere'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 n1. For example, to compute F_{6}, find all the sequences of ones and twos that add up to 5 (since 61=5). They are 11111, 1112, 1121, 1211, 122, 2111, 212, 221. There's 8 of them, and so F_{6} 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. A picture sometimes helpsSometimes a picture helps. For example, drawing a picture makes it clear that the sequence with n^{th} 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
1^{2}+1^{2}+2^{2}+3^{2}+…+F_{n}^{2}=F_{n}F_{n+1}.
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
A generating function f for the infinite sequence The generating function for the Fibonacci sequence is x / (1  x  x^{2}). 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 03405508914423337761098859958818777596374One 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" . The geometric sequenceA geometric sequence x_{0}, x_{1}… is one in which the first term x_{0} is arbitrary, usually denoted by "a", and the ratio of terms x_{n}/x_{n1} is a constant, usually denoted by "r". ie x_{n} = r x_{n1}x_{0} = a Equivalently, in terms of powers, x_{n} = a r^{n}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 20^{th} 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 x_{0} + x_{1} + x_{2} + x_{3} + … + x_{n} = (x_{n+1}  x_{0}) / (r  1)
This follows from realizing that rS_{n}  S_{n} = ar^{n+1}  a , for One possible way to discover this for yourself is by playing around with the sum S_{n} and noticing that rS_{n} has almost exactly the same terms as S_{n}. Once you realize that, taking their difference to get a simple expression is hard to avoid (he says with the benefit of hindsight). Relevance of the geometric sequenceThe 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 G_{n} = ar^{n} and substituting into the recurrence G_{n} = G_{n1} + G_{n2}, we get ar^{n} = ar^{n1} + ar^{n2}.This immediately simplifies to the quadratic equation for the golden ratio r^{2} = r + 1So, 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 n^{th} term is a φ^{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 (G_{0},G_{1})=(1,0) and another with (G_{0},G_{1})=(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! Projection of a two dimensional geometric sequenceThe 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 X_{n} (a sequence of two dimensional points) and F (a linear transformation) are given by
X_{n} = F X_{n1} should look familiar: it's the recurrence equation for a geometric series. Just like before, we have X_{n} = F^{n} X_{0}. There are analogues of results for the one dimensional geometric sequence in the two dimensional case. One example is that S_{n}, the sum of terms from X_{0} to X_{n} 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
Some ContextThis 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 spacetime 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 spacetime geodesic. Some consequencesWhat 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. Summation identityThe first candidate is the summation formula G_{0} + G_{1} + … + G_{n} = G_{n+2}  G_{1}As mentioned above, the sum of a geometric series is given by X_{0} + X_{1} + … + X_{n} = ( F  I )^{1} (X_{n+1}  X_{0})Since F satisfies the golden ratio quadratic ie F^{2} = F + I, we have F = (F  I)^{1}, and so X_{0} + X_{1} + … + X_{n} = F (X_{n+1}  X_{0}) = X_{n+2}  X_{1}The projection of this to the y axis P_{y}(X_{0} + X_{1} + … + X_{n}) = P_{y}(X_{n+2}  X_{1})is the summation result for the Generalized Fibonacci sequence G_{0} + G_{1} + … + G_{n} = G_{n+2}  G_{1}Efficient computationThe second candidate is the efficient computation of the Fibonacci numbers. A naive approach is to use the linear time iterative approach: use F_{0} and F_{1} to get F_{2}, then use F_{1} and F_{2} to get F_{3} and so on until we get F_{n}. In fact, there's a logarithmic time algorithm, and it's just the projection of the logarithmic time algorithm for computing the n^{th} term of a geometric sequence, namely repeated squaring. In case you haven't seen this before, here are more details: r^{n}, for n greater than 1, can be computed as (r^{n/2})^{2} for n even, and (r)(r^{n1}) for n odd. Recursing down to n=1, it follows that 2 log_{2}(n) multiplications are enough to compute r^{n}. Discovering Binet's formulaAs 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 X_{0} as a linear combination (a v + b w) of v and w, and using the fact that X_{n} = F^{n} X_{0}, 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. [ * ] Using inner products to get a resultThe 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 or, equivalently 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 F_{2n+1} = F_{n+1}^{2} + F_{n}^{2} ) in the combinatorial section Incidentally, a more symmetric way of expressing the general identity is whenever a+b = m+n. Concluding wordsJust 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. Feedback[ 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:walterv@gbbservices.com
