The great Italian mathematician, Leonardo of Pisa (c. 1170-1250), who is known today as Fibonacci (an abbreviation of filius Bonacci), expanded on the Arabic algebra of North Africa and introduced algebra into Europe. The solution of a problem in his book Liber Abacci uses the sequence

(F)                                                               0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

One of the many applications of this Fibonacci sequence is a theorem about the number of steps in an algorithm for finding the greatest common divisor of a pair of large integers. We study the sequence here because it provides a wonderful opportunity for discovering mathematical patterns.

The numbers shown in (F) are just the beginning of the unending Fibonacci sequence. The rule for obtaining more terms is as follows:

RECURSIVE PROPERTY. The sum of two consecutive terms in (F) is the term immediately after them.

For example, the term after 55 in (F) is 34 + 55 = 89 and the term after that is 55 + 89 = 144.

To aid in stating properties of the Fibonacci sequence, we use the customary notation F₀, F₁, F_2, F₃, for the integers of the Fibonacci sequence. That is, F₀ = 0, F₁ = 1, F₂ = F₀ + F₁ = 1, F₃ = F₁ + F₂ = 2, F₄ = F₂ + F₃ = 3, F₅ = F₃ + F₄ = 5, F₆ = F₄ + F₅ = 8, and so on. When F_n stands for some term of the sequence, the term just after F_n is represented by F_n+1, the term after F_n+1 is F_n+2, and so on. Also, the term just before F_n is F_n-1, the term just before F_n-1 is F_n-2 and so on.

We now can define the Fibonacci numbers formally as the sequence F₀, F₁, ... having the two following properties.

INITIAL CONDITIONS F₀ = 0 and F₁ = 1.

RECURSION RULE F_n + F_n+1 = F_n+2 for n = 0, 1, 2, ... .

Next let S_n stand for the sum of the Fibonacci numbers from F₀ through F_n. That is,

and in general, S_n = F₀ + F₁ + F₂ + ... + F_n = S_n-1 + F_n.

We tabulate some of the values and look for a pattern.

Is there a relationship between the numbers on the third line of this table and the Fibonacci numbers? One pattern is that each of the terms of the sequence S₀, S₁, S₂, ... is 1 less than a Fibonacci number. Specifically, we have

and might conjecture that S_n = F_n+2 - 1 for n = 0, 1, 2, ... . Does this formula hold for n = 6? Yes, since

The first steps in proving our conjecture correct for all the terms in the unending sequence S₀, S₁, S₂, ... are rewriting the recursion formula F_n + F_n+1 = F_n+2 as F_n = F_n+2 - F_n+1 and then using this to replace each Fibonacci number in the sum S_n by a difference as follows:

Next we rearrange the terms and get

Thus we have made our conjecture (that is, educated guess) into a theorem.

.

Wednesday, May 24, 2000