﻿ Fibonacci Numbers


He was the greatest European mathematician of the Middle Ages. He lived in Pisa, at a time—about 1170 to about 1250—when Europeans were beginning to use Arabic numerals. His book Liber Abaci was a widely used introduction to this exciting new technology.

What to call him can be a confusing matter. His first name is easy: Leonardo, or Leonard, or Leonardus. But Italian usage of last names was very flexible, then and for a long time afterward. Here are some versions that were official enough to appear on manuscripts of his books.

The Fibonacci sequence

The Fibonacci sequence (Fn, n= 0,1, ... ) satisfies F0 = 0, F1 = 1, and

Fn+2 = Fn+1 + Fn .

Here is a brief table of values of Fn .

Fn 0 1 1 2 3 5 8 13 21 34 55 89

The Fibonacci numbers are related to the golden ratio, which will be denoted here by τ.

Fibonacci numbers in terms of τ

The recurrence relation An+2 = An+1 + An is satisfied if we let An = Fn; it is also satisfied if we let An = τn. This is because τ is a solution of

x2 = x + 1 .

Now that is a quadratic equation, so it has a second solution, which turns out to be -ρ = -τ-1 . Therefore the recurrence relation is also satisfied if we let An = (-τ)-n.

That recurrence relation is a linear equation, so two solutions to it can be combined, with arbitrary constant factors. If we put together the two solutions we just found in this way:

un = (τn - (-τ)-n)/ √5 ,

then we find that u0 = 0 and u1 = 1; from this it follows that Fn = un.

Approximation to τ using Fibonacci numbers

Because τ > 1, positive powers of τ dominate negative powers, and so that expression for Fn implies that for large n, Fn is close to n)/√5. Therefore Fn+1/Fn is approximately τ.

Powers of τ and Fibonacci numbers

Although τ is an irrational number, computation with it is not difficult, and expressions involving τ can often be simplified. For instance, consider the powers of τ. We already have used the fact that τn+2 = τn+1 + τn ; we can apply it to reduce powers of τ thus:

τ0 = 1
τ1 = τ
τ2 = τ + 1
τ3 = + 1
τ4 = + 2
τ5 = + 3
τ6 = + 5
τ7 = 13τ + 8

and so on; in general,

τn = Fnτ + Fn-1 .

The negative powers of τ are found similarly, using the recurrence relation in the form τ−n = −τ−(n−1) + τ−(n−2). We find:

τ0 = 1
τ−1 = τ 1
τ−2 = −τ + 2
τ−3 = 3
τ−4 = −3τ + 5
τ−5 = 8
τ−6 = −8τ + 13
τ−7 = 13τ 21

and so on; in general,

τ−n = (−1)nFnτ + (−1)n+1Fn+1 .

Approximation of τ revisited

From these expressions for powers of τ, we can get a better idea of how good the approximate values of τ are. For example, we see that 13τ − 21 = τ−7. This implies

τ = 21/13 + 1/(13τ7).

How big is the error term? Well, we have an expression for τ7, namely 13τ+8; and we know that 13τ is close to 21. Therefore the error term is close to

1/(13(21+8)) = 1/377.

Hmm, 377 = F14. Coincidence? I think not...

Some references

Conway, John Horton and Guy,Richard K., The Book of Numbers, New York, Copernicus Books, 1997; pp. 113-126.

Gardner, Martin, The 2nd Scientific American Book of Mathematical Puzzles and Diversions, New York, Simon & Schuster, 1961; chapter 8.

Gies, Joseph and Gies, Frances, Leonard of Pisa, Gainesville, Georgia, Elliott Wave International, Inc., 1983.

Graham, Ronald L., Knuth, Donald E., and Patashnik, Oren , Concrete Mathematics, second ed., Reading, Massachusetts, Addison-Wesley Longmans, 1997; section 1.2.8.

Knuth, Donald E., The Art of Computer Programming, vol. 1, Reading, Massachusetts, Addison-Wesley Longmans, 1997; section 1.2.8.

Sigler, Laurence, Fibonacci's Liber Abaci: A Translation into Modern English of Leonardo Pisano's Book of Calculation, New York, Springer Verlag, 2004.

Stewart, Ian, Letters to a Young Mathematician, New York, Basic Books, 2006.

Last modified on $Date: 2011-09-22 19:55:11 -0400 (Thu, 22 Sep 2011) $

Christopher J. Henrich