Fibonacci Numbers

Fibonacci Numbers

by: Stephanie J. Morris

Fibonacci numbers and the Fibonacci sequence are prime examples of "how mathematics is connected to seemingly unrelated things." Even though these numbers were introduced in 1202 in Fibonacci's book Liber abaci, they remain fascinating and mysterious to people today.

Fibonacci, who was born Leonardo da Pisa "son of Bonaccio", gave a problem in his book whose solution was the Fibonacci sequence as we know it today. The now famous problem appeared in Liber abaci which

was one of the first works on equations to be published by a European.

Fibonacci's Problem:

"Start with a pair of rabbits, (one male and one female) born on January 1. Assume that all months are of equal length and that :

1. rabbits begin to produce young two months after their own birth;

2. after reaching the age of two months, each pair produces a mixed pair, (one male, one female), and then another mixed pair each month thereafter; and

3. no rabbit dies.

How many pairs of rabbits will there be after one year?"

Fibonacci's Solution: The Fibonacci Sequence!

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

So, at the end of the year, there will be 144 pairs of rabbits, all resulting from the one original pair born on January 1 of that year.

Each term in the Fibonacci sequence is called a Fibonacci number. As can be seen from the Fibonacci sequence, each Fibonacci number is obtained by adding the two previous Fibonacci numbers together. For example, the next Fibonacci number can be obtained by adding 144 and 89. Thus, the next Fibonacci number is 233.

The recursive definition for generating Fibonacci numbers and the Fibonacci sequence is:

fn = fn-1 + fn-2 where n>3 or n=3

and

1. n = the number of the term, for example, f3 = the third Fibonacci number; and

2. f 1 = f2 = 1

One of the most fascinating things about the Fibonacci numbers is their connection to nature. Some items in nature that are connected to the Fibonacci numbers are:

- the growth of buds on trees

- the pinecone's rows

- the sandollar

- the starfish

- the petals on various flowers such as the cosmo, iris, buttercup, daisy, and the sunflower

- the appendages and chambers on many fruits and vegetables such as the lemon, apple, chile, and the artichoke

The Fibonacci sequence and the Fibonacci numbers also have many interesting mathematical properties.

Mathematical Properties of the Fibonacci Sequence:

I. The Binet Formula:

fn = (1+5)/2 - (1-5)/2

where (1+5)/2 is the golden ratio

From the sequence, we know that f3 = 2.

Using Binet's Formula,

f3 = (1+5)/2 - (1-5)/2

= (1+3 5+15 +5 5) - (1-3 5+15 -5 5)

8 8

__________________________________

= 2

II. f1 + f2 +...+ fn-1 + fn = fn+2 -1.

Proof:

f1 = f3 - f2, (f3 = f1 + f2),

f2 = f4 - f3,

f3 = f5 - f4,

.......................

fn-1 = fn+1 - fn,

fn = fn+2 - fn+1,

By adding each of these terms, we get the desired result.

Example:

f1 + f2 + f3 = f5 - 1

1 + 1 + 2 = 4 = 5 - 1.

III. The sum of the first n Fibonacci numbers with odd indices is

f1 + f3 +...+ f2n-1 = f2n.

The proof is similar to the proof in II.

Example:

f1 + f3 + f5 = 1+ 2 + 5

= 8

= f6 .

IV. The sum of the first n Fibonacci numbers with even indices is

f2 + f4 + ... + f2n = f2n+1 - 1.

Proof:

From II,

f1 + f2 + f3 + ... + f2n = f2n+2 - 1.

When we subtract the result from III, we get the desired result.

Example:

f2 + f4 + f6 + f8 + f10 + f12 = 1 +3 + 8 + 21 +55 +144

= 232

= f13 - 1 .

V. The sum of all (fn+1)/ (fn )

converges to the Golden Ratio.

3/1 + 5/3 + 8/5 + 13/8 .... converges to ) / 2.

Proof that Rn converges to the Golden Ratio:

Let R = lim Rn as n approaches infinity

= lim f n+1 / f n as n approaches infinity

= lim fn + fn-1 /fn as n approaches infinity

= lim (1 + fn-1/ fn) as n approaches infinity

= 1 + lim (fn-1 /fn ) as n approaches infinity

= 1 + 1/ lim (fn-1 /fn ) as n approaches infinity

= 1 + 1/R

So, R = 1 + 1/R,

or R^2 = R + 1,

R^2 - R - 1 = 0,

R = ( ) / 2

= ( ) / 2

Since Rn is positive, Rn = ( ) / 2 .

Thus, Rn converges to the Golden Ratio.

Number Theory Properties of the Fibonacci Sequence:

Theorem 1 : If n is divisible by m, then fn is divisible by fm.

Proof by Induction:

Let n be divisible by m, i.e., n = m * k where k is some integer.

Assume that fm * fk is divisible by fm .

Consider fm * fk + 1.

fm (k + 1) = fmk + m.

and fmk + m = fmk -1fm + fmkfm + 1

Since fmk -1fm is divisible by fm, fmk1fm + 1 is also divisible by fm.

Theorem 2 : Consecutive Fibonacci numbers are relatively prime.

Proof by Contradiction:

Assume that there exist some two consecutive Fibonacci numbers say

fn and fn+1 that have a common divisor d, where d is greater than 1.

Thus, their difference fn+1 - fn = fn-1 will also be divisible by d.

However, we know that f1=1 which is clearly not divisible by d. Thus, we have reached a contradiction. Therefore, consecutive Fibonacci numbers are relatively prime.

The Euclidean Algorithm and the Fibonacci Sequence:

Consider the following Fibonacci numbers:

1 = 1 * 1

1 = 1 * 1 + 0

2 = 1 * 1 + 1

3 = 1 * 2 + 1

5 = 1 * 3 + 2

8 = 1 * 5 + 3

13 = 1 * 8 + 5

................................

fn-1 = 1*fn-2 + fn-3

fn = 1*fn-1 + fn-2

fn+1 = 1*fn + fn-1

Therefore, the Euclidean Algorithm can be used to express Fibonacci numbers. By reversing the process, (final step to first step), it can be seen that it is relatively prime. The Fibonacci sequence can also be used to test for primality, namely with the Lucas N+1 primality test.

The Fibonacci sequence can also be used on the spreadsheet. Using the spreadsheet, one can find any Fibonacci number.

So, if one wanted to know how pairs of rabbits there would be at the end of 25 months, the answer, 75,025, could be found using the spreadsheet.

The Fibonacci numbers have many mathematical properties that are worthy of exploration in today's mathematics curriculum. They can be explored in many courses and mathematical contexts. Fibonacci numbers can easily provide many worthwhile mathematical tasks for students.

Bibilography

Dion, Gloria S. . Fibonacci Meets the TI-82: : Mathematics Teacher

February 1995. Reston, VA.

"Those Fascinating Fibonaccis!" NCTM: Student Math Notes. January

1996, Reston, VA.

The Fibonacci Quartely, February 1995.