Fibonacci Numbers

Fibonacci, also known as Leonardo of Pisa, was one of the greatest European mathematicians of the middle ages. His book on arithmetic played a major role in the spreading of Hindu-Arabic numerals into Europe. In 1202, he posed the following problem:

A male and a female rabbit are born at the beginning of the year. We assume the following conditions:

Rabbit pairs are not fertile during their first month of life, but thereafter give birth to one new male/female pair at the end of every month.

No deaths occur during the year.

How many rabbits will there be at the end of the year?

If we let F(n) denote the number of rabbit pairs at the beginning of month n, then we have

F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5,...

and,in general,

F(n+2)=F(n)+F(n+1).

The sequence {1,1,2,3,5,8,...} generated according to this scheme was named in honor of Fibonacci. The Fibonacci sequence was one of the earilest examples of a recursively defined sequence. There are many other examples in population dynamics where the Fibonacci sequence arises.

The first 55 Fibonacci numbers are given in the following table:

n, F(n)	n, F(n)	n, F(n)	n, F(n)	n, F(n)
1, 1	12, 144	23, 28657	34, 5702887	45, 1134903170
2, 1	13, 233	24, 46368	35, 9227465	46, 1836311903
3, 2	14, 377	25, 75025	36, 14930352	47, 2971215073
4, 3	15, 610	26, 121393	37, 24157817	48, 4807526976
5, 5	16, 987	27, 196418	38, 39088169	49, 7778742049
6, 8	17, 1597	28, 317811	39, 63245986	50, 12586260925
7, 13	18, 2584	29, 514229	40, 102334155	51, 20365011074
8, 21	19, 4181	30, 832040	41, 165580141	52, 32951280099
9, 34	20, 6765	31, 1346269	42, 267914296	53, 53316291173
10, 55	21, 10946	32, 2178309	43, 433494437	54, 86267571272
11, 89	22, 17711	33, 3524578	44, 701408733	55, 139583862445

The first 500 Fibonacci numbers can be found here.

The Fibonacci sequence arises in many applications. It has some very interesting and peculiar properties.

On many flowers, the number of petals is a Fibonacci number.
Fibonacci numbers can also be seen in the arrangement of seeds on flowerheads.
Many plants show the Fibonacci numbers in the arrangements of the leaves around the stems.

Consecutive Fibonacci numbers give the worst case behavior when they are used as inputs in the Euclidean algorithm. (Recall that the Euclidean algorithm is used to find the GCD of two positive integers.)
As n approaches infinity, the ratio F(n+1)/F(n) approaches the golden ratio (f=1.6180339887498948482...). The Greeks felt that rectangles whose sides are in the golden ratio are aesthetically most pleasing.
The Fibonacci number F(n+1) gives the number of ways for 2 x 1 dominoes to cover a 2 x n checkerboard.
The sum of the first n Fibonacci numbers is F(n+2)-1.
The "shallow" diagonals of Pascal's triangle sum to Fibonacci numbers.
(Except for the case n=4) If F(n) is prime, then n is prime. Equivalently, if n is not prime, then F(n) is not prime.
gcd( F(n), F(m) ) = F( gcd(n,m) )

A great deal of information is available on the Fibonacci numbers. Here are some excellent sites to visit:

The Fibonacci Numbers and the Golden section

Fibonacci Number

Fibonacci - A biography.

Fibonacci - Another biography.

Steve Kifowit
Prairie State College
Chicago Heights, IL 60411