﻿ Fibonacci Numbers

# Fibonacci

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.

• Leonardus filius Bonaccii, that is, "Leonardo Fibonacci," literally "Leonard son of Bonaccio." According to Gies and Gies, "Fibonacci" was really a family name. Well, maybe. According to Ian Stewart, this name was probably invented in the nineteenth century. Scholars love hard facts, not least because they are rare.
• Leonardus Pisanus, that is, "Leonard the Pisan" or "Leonardo of Pisa."
• Leonardus Bigollus. According to Gies and Gies, "Bigollus" means something like "absent-minded." Lenny the nerd?

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

 n 0 1 2 3 4 5 6 7 8 9 10 11 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 = 2τ + 1 τ4 = 3τ + 2 τ5 = 5τ + 3 τ6 = 8τ + 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 = 2τ − 3 τ−4 = −3τ + 5 τ−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