The Fibonacci Numbers Revisited

Introduction

The Fibonacci numbers are

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

They're usually denoted F₀, F₁, F₂, F₃, F₄, … 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 sequences

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 L₀, L₁, L₂, L₃, L₄,…

Finally, given constants G₀ and G₁, the resulting Generalized Fibonacci sequence generated by the Fibonacci recurrence relationship is usually denoted G₀, G₁, G₂, G₃, G₄,… Of course, G₀=0, G₁=1 gives the standard Fibonacci sequence, while G₀=2, G₁=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.

The recursive definition

F_n = F_n-1 + F_n-2
F₀ = 0
F₁ = 1

Enough said!

Binet's formula

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 x² - 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:

F_n = (φⁿ − (1-φ)ⁿ ) / √5

The corresponding formula for Lucas numbers is

L_n = φⁿ + (1-φ)ⁿ

For a Generalized Fibonacci sequence,it's always possible to find constants a and b for which

G_n = a φⁿ + b (1-φ)ⁿ

One way to see that this is true is described later in this essay.

Note that since

lim _n→∞ φⁿ = ∞

and

lim _n→∞ (1-φ)ⁿ = 0

we have that

lim _n→∞ F_n+1/ F_n = φ

This is not so clear via the inductive definition.

Another immediate consequence of these formulas for the Fibonacci and Lucas sequences is the relationsip

F_nL_n = F_2n

It follows from the algebraic identity (x-y)(x+y) = x²-y² as follows:

F_nL_n=((φⁿ − (1-φ)ⁿ ) / √5) (φⁿ + (1-φ)ⁿ)= (φ²ⁿ − (1-φ)²ⁿ ) / √5 = F_2n

A combinatorial characterization

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 F₆, 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 F₆ 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² + F_n+1² = 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 2n-1 (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² of them) and the number of strings that have middle character "B" (there are F_n² of them). It can also be used to derive an unlimited number of similar results like

F_n+1F_2n+1 + F_n+2F_2n+2 = F_3n+3 .

Another combinatorial characterization

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 F₆, 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 F₆ 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

Fn+1	=	(	n	)	+	(	n-1	)	+	(	n-2	)	+	…	=	Σ		(	n-k	)
			0				1				2						{k ≥ 0 and 2k ≤ n}		k

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 helps

Sometimes a picture helps. For example, drawing a picture makes it clear that the sequence with n^th term

Σ		(	n-k	)
	{k ≥ 0 and 2k ≤ n}		k

must satisfy the Fibonacci recurrence. Here's the picture:

											1
										1		1
									1		2		1
								1		3		3		1
							1		4		6		4		1
						1		5		10		10		5		1
					1		6		15		20		15		6		1
				1		7		21		35		35		21		7		1
			1		8		28		56		70		56		28		8		1
		1		9		36		84		126		126		84		36		9		1

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²+1²+2²+3²+…+F_n²=F_nF_n+1.
I know of no better way to understand it than the following picture

12	12	32	82
22
52

There's a generalization involving Generalized Fibonacci numbers:
G₁²+G₂²+G₃²+G₄²+…+G_n² = G_nG_n+1 - G₀G₁
Again, a picture makes it clear why

G0G1	G22	G42
G12
G32

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
a₀, a₁, a₂, a₃, a₄…
is one which has a power series expansion of the form
f(x) = a₀ + a₁ x + a₂ x² + a₃ x³ + …

The generating function for the Fibonacci sequence is x / (1 - x - x²).

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

The geometric sequence

A geometric sequence x₀, x₁… is one in which the first term x₀ is arbitrary, usually denoted by "a", and the ratio of terms x_n/x_n-1 is a constant, usually denoted by "r". ie

x_n = r x_n-1
x₀ = a

Equivalently, in terms of powers,

x_n = a rⁿ

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₀ + x₁ + x₂ + x₃ + … + x_n = (x_n+1 - x₀) / (r - 1)

This follows from realizing that rS_n - S_n = arⁿ⁺¹ - a , for
S_n = x₀ + x₁ + x₂ + x₃ + … + x_n

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 sequence

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 G_n = arⁿ and substituting into the recurrence G_n = G_n-1 + G_n-2, we get

arⁿ = ar^n-1 + ar^n-2.

This immediately simplifies to the quadratic equation for the golden ratio

r² = 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 n^th term is

a φⁿ + b (1-φ)ⁿ

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₀,G₁)=(1,0) and another with (G₀,G₁)=(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 sequence

The linear recurrence

G_n+1 = G_n + G_n-1

can be rewritten in matrix form as

[	Gn+1	]	=	[	1	1	]	[	Gn	]
									Gn-1

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

[	Gn+1	]	=	[	1	1	]	[	Gn	]
	Gn				1	0			Gn-1

This is of course the same as

X_n = F X_n-1

where X_n (a sequence of two dimensional points) and F (a linear transformation) are given by

Xn	=	[	Gn+1	]	and	F	=	[	1	1	]
			Gn						1	0

X_n = F X_n-1 should look familiar: it's the recurrence equation for a geometric series.

Just like before, we have X_n = Fⁿ X₀. 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₀ to X_n is given by pretty much the same formula as before

S_n = ( F - I )^-1 (X_n+1 - X₀)

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

Py

=

[

0

1

]

In terms of this operator, we can write

[

Gn

]

=

[

0

1

]

[

Gn+1

]

=

[

0

1

]

Xn

=

Py

Xn

Gn

Some Context

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

[

cos(α+β)

-sin(α+β)

]

[

1

]

=

[

cos(β)

-sin(β)

]

[

cos(α)

-sin(α)

]

[

1

]

sin(α+β)

cos(α+β)

0

sin(β)

cos(β)

sin(α)

cos(α)

0

Projecting to the y axis, we get the well known identity

sin(α+β) = sin(β)cos(α)+cos(β)sin(α).

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.

Some consequences

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.

Summation identity

The first candidate is the summation formula

G₀ + G₁ + … + G_n = G_n+2 - G₁

As mentioned above, the sum of a geometric series is given by

X₀ + X₁ + … + X_n = ( F - I )^-1 (X_n+1 - X₀)

Since F satisfies the golden ratio quadratic ie F² = F + I, we have F = (F - I)^-1, and so

X₀ + X₁ + … + X_n = F (X_n+1 - X₀) = X_n+2 - X₁

The projection of this to the y axis

P_y(X₀ + X₁ + … + X_n) = P_y(X_n+2 - X₁)

is the summation result for the Generalized Fibonacci sequence

G₀ + G₁ + … + G_n = G_n+2 - G₁

Efficient computation

The second candidate is the efficient computation of the Fibonacci numbers. A naive approach is to use the linear time iterative approach: use F₀ and F₁ to get F₂, then use F₁ and F₂ to get F₃ 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ⁿ, for n greater than 1, can be computed as (r^n/2)² for n even, and (r)(r^n-1) for n odd. Recursing down to n=1, it follows that 2 log₂(n) multiplications are enough to compute rⁿ.

Discovering Binet's formula

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

F (a v + b w) = φ a v + (1-φ) b w

for all scalars a and b.

Writing X₀ as a linear combination (a v + b w) of v and w, and using the fact that X_n = Fⁿ X₀, we have

X_n = φⁿ a v + (1-φ)ⁿ b w

Projecting to the y axis, we get

P_y X_n = φⁿ ( a P_y v ) + (1-φ)ⁿ ( b P_y w )

In other words, there are constants A and B for which

G_n = φⁿ A + (1-φ)ⁿ B

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 result

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

< F v , w > = < v ,F w >

where < v , w > is the usual Euclidean inner product.

It follows immediately that

< X₀ , F^m+n X₀ > = < F^m X₀ , Fⁿ X₀ >

or, equivalently

< X₀ , X_m+n > = < X_m , X_n >

This is just the Generalized Fibonacci identity

G₁ G_m+n+1 + G₀ G_m+n = G_m+1 G_n+1 + G_m G_n

The special case for the Fibonacci numbers is of course

F_m+n+1 = F_m+1 F_n+1 + F_m F_n

You might remember that we saw the case where m=n ( ie F_2n+1 = F_n+1² + F_n² ) in the combinatorial section

Incidentally, a more symmetric way of expressing the general identity is

G_a+1 G_b+1 + G_a G_b = G_m+1 G_n+1 + G_m G_n

whenever a+b = m+n.

Concluding words

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

Fn	=	[	Fn+1	Fn	]
			Fn	Fn-1

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