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:

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

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

## Applications

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