The Fibonacci Sequence



The Fibonacci Sequence

By Leslie Quinn

April 12, 2005

MATH 4010

In the twelfth century, Europe was beginning to emerge, little by little, from medieval thinking; an age known for a lax in concern for global education and rise in religious crusades and conquests in general. Great strides were being made in Italy in education, with the opening of many new institutes of higher learning[1], and commerce was booming in the Eastern hemisphere, especially along the Mediterranean where there was a commercial revolution[2].

While the conflict between the Papacy and the Holy Roman Empire was dieing down, many Italian cities were left as independent city-states, and turned to trade and other endeavors to sustain their economies. One such city-state was Pisa[3]. Pisa is located conveniently on the Mediterranean which makes it easily accessible for trade by boat and land. As Pisa was beginning to grow economically due to many great commercial endeavors, it, as well as other parts of Western Europe, was also beginning to awake from its intellectual slumber. While the great minds of Euclid and Ptolemy were resurfacing in England[4], in the city-state of Pisa another magnificent mind was being born.

Leonardo of Pisa was born around 1175 AD, though no-one knows for certain the exact date. He is perhaps best known to mathematicians as Fibonacci, which is short for Filius Bonacci, meaning son of Bonaccio[5] (Bonacci being plural for Bonaccio, which is assumed to be a family name). Leonardo sometimes referred to himself as Leonardo Bigollo, which means traveler.[6] Not much is known about his father, Guilielmo Bonacci, but that he benefited occupationally from the commercial revolution by working as a customs officer, or state official for merchants of Pisa by overseeing Pisan trade in Bugia, present day BejaIa, Algeria, in northern Africa. While growing up in Northern Africa Leonardo’s father instilled the importance of mathematics to him, and thus Leonardo was educated there in the Hindu-Arabic mathematical system.

Later, it is said, Leonardo traveled across the Mediterranean, and joined up with many merchants to learn their mathematical systems[7]. It was there in his youth that he became fascinated with Hindu-Arabic notation, and its ease of use as compared to the Roman numeral system that was being used in Pisa, and all other systems he came across. Upon realizing the advantages to Hindu-Arabic notation and his return to Pisa in 1200, he began writing texts which would prove to be a huge contribution to mathematics.

Because Leonardo lived before the invention of the printing press, his works were hand copied, and for this reason only a few exist today. Among his existing works are: Liber Abaci, 1202, Practica Geometriae, 1220, Flos, 1225, and Liber Quadratorum[8].

Leonardo’s most famous and influential book is Liber Abaci, meaning “book of calculations”. The original was published in 1202, but it is his revision that was published 26 years later that we know today [7]. At the time Liber Abaci was written, Roman and Greek mathematics were dominant in Europe, and Fibonacci, as well as some others, felt that dealing with Roman numerals was extremely cumbersome. Liber Abaci was intended to introduce Hindu-Arabic numerals to Europe in a manner that would convince them to convert their current mathematical system. He was not the first to try and accomplish this huge feat, but he is definitely credited with achieving it. Many credit the style in which the materials in Liber Abaci were presented that eventually inspired a change.

This book consists of fifteen chapters of elementary arithmetic and algebra, mostly taken from Arabic and Asian sources, in a basic how to manual of Hindu-Arabic mathematical procedures. It opens:

Begin the first chapter. The nine Hindu figures are 9, 8, 7, 6, 5, 4, 3, 2, 1. It is shown below (how) to write any number with (just) these nine figures and the sign 0, which the Arabs called “cipher”[2]

It appears that Leonardo had a book from each of the fields of arithmetic and algebra to use for reference in his book. His biggest influence was the book Algebra by Abū Kāmil, written in 900 AD. He used 29 examples from Algebra in his writing of Liber Abaci [2].

The popularity of Liber Abaci was not only due to its persuasive descriptions of Hindu-Arabic equations, but also due to one of the problems it contained that would end up having a profound influence on mathematicians and scientists alike. This problem is referred to as the famous rabbit problem which led to the popularization and global awareness of the famous Fibonacci Sequence which is the topic of much of the remainder of this paper. Though Leonardo put little effort into properties of the famous sequence that bears his name, it has been found to contain in itself a seemingly infinite amount of importance.

In the third section of Liber Abaci, chapter 12, Leonardo introduces the famous Rabbit Problem. Most likely this problem was copied out of an Arabic or Eastern text, but it was this publication that led to its popularity and in turn the popularity of Leonardo and his Fibonacci Sequence.

Rabbit Problem

How Many Pairs of Rabbits Are Created by One Pair in Each Year

A certain man had one pair of Rabbits together in a certain enclosed place, and one wishes to know how many are created from the pair in one year when it is the nature of them in a single month to bear another pair, and in the second month those born to bear also [10][9].

Leonardo’s original solution as translated is:

Because the abovewritten pair in the first month bore, you will double it;

there will be two pairs in one month.

One of these, namely the first, bears in the second month, and thus there are in the second month 3 pairs;

Of these in one month two are pregnant and in the third month 2 pairs of rabbits are born, and thus there are five pairs in the month;

…

there will be 144 pairs in this [the tenth] month;

to these are added again the 89 pairs that are born in the eleventh month;

there will be 233 pairs in this month,

To these are still added the 144 pairs that are born in the last month;

there will be 377 pairs, and this many pairs are produced from the abovewritten pair in the mentioned place at the end of the one year[10]10.

The following table illustrates population growth of the rabbits in one year’s time:

|Month |Grown Rabbits |New Babies |Total Pairs |

|Original |1 |0 |1 |

|January |1 |1 |2 |

|February |2 |1 |3 |

|March |3 |2 |5 |

|April |5 |3 |8 |

|May |8 |5 |13 |

|June |13 |8 |21 |

|July |21 |13 |34 |

|August |34 |21 |55 |

|September |55 |34 |89 |

|October |89 |55 |144 |

|November |144 |89 |233 |

|December |233 |144 |377 |

The Column to the far right, total pairs, represents what would later be labeled the Fibonacci Sequence by Edouard Lucas in 1878. Since this sequence has been named it has been found that this it was also discovered by such men as Euler, Virgil, and Johann Kepler, all independent of each other.

At first glance one may wonder what is so special about this sequence and what does it all mean? These questions will surely be answered in the following pages.

The Fibonacci Sequence in its original notation is as follows:

|[pic], |f0 = 1 |[pic], |[pic], |[pic], |[pic], |[pic], |

| |[pic], | | | | | |

and so on[10]…

By inspection you will notice that[pic], for n ≥ 0. This is called a recursive sequence, which means that each number in the sequence (from [pic] and on in this case) is the sum of the previous two numbers. The Fibonacci Sequence is said to be the first recursive sequence ever discovered.

The rabbit problem is essentially asking the solver to find how many pairs of rabbits will exist at the end of the year, or the value of[pic]which, as Fibonacci states and is shown in the table, is 377. This problem was most likely originally tediously solved by Fibonacci, in the arithmetic fashion shown above. However, since Fibonacci there has been a lot of attention drawn to this sequence, and thus there now exists a formula to find the nth Fibonacci number. This formula was discovered by a few mathematicians including Euler and Bernoulli independently of each other, but today it is called Binet’s formula:

It can also be written in terms of[pic]and[pic], where [pic] = [pic]and [pic]= [pic]:

[pic] [3]

But to better understand this formula let us discuss the value of[pic], commonly referred to as [pic], also known as the golden ratio, golden mean, or golden section.

Phi

First we should observe that[pic]and[pic] are the roots to the equation:

[pic], or [pic] (1)

One of the astonishing properties of the Fibonacci Sequence is that the sequence of ratios of two successive terms converges, meaning that as you calculate the ratios of the greater term to the previous lesser term these numbers become arbitrarily close to one number, and that number is[pic]. Observe:

Fractional Ratios:

[pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], [pic], …, [pic]

Decimal Ratios:

2, 1.5, [pic], 1.6, 1.625, 1.615384615, …, 1.618037135, …, 1.618033989, …

Approximation of phi:

[pic] [pic]1.618033989

The last number in the decimal sequence is the ratio of the 24th term and the 23rd term in the Fibonacci Sequence and approximates[pic]correctly to nine decimal places. This number, as stated previously, is known as the golden ratio. Even as far back as ancient Greece[pic]:1 has been thought of as the most aesthetically pleasing ratio in art and architecture, as well as in nature[14].

It is also interesting to observe in what other ways the Fibonacci sequence, and other recursive sequences relate to equation (1) and the golden ratio:

Let us define a recursive function:

[pic], for [pic]

Say we divide through by a term such as[pic], then we have:

[pic][pic][pic]

very interesting[17].

Not only is it fascinating that the Fibonacci sequence converges to the golden ratio, which is a root of the above equation, but there are many fascinating properties of [pic] that are useful in proving Binet’s formula (I will use[pic]in place of[pic] in the following properties to better relate to the form of Binet’s formula that will be used in the proof):

[pic] (2)

[pic] (3)

[pic] (4)

[pic] (5)

[pic] (6)

[pic] (7)

[pic] (8)

and so on… (There are many other interesting properties of[pic] which are not addressed here).

Now that we know some information about [pic]and [pic] we can see how Binet and others related these terms to the Fibonacci sequence.

Proving Binet Right

Binet’s formula can be proven in many different ways. One of the most basic ways is by using the principle of mathematical induction. To prove the formula in this way let us start out by defining the Fibonacci sequence in modern notation, so:

[pic] for all [pic].

Theorem: [pic], for all [pic], where [pic] = [pic]and [pic]= [pic]

Proof: Let n = 0, then[pic]. Now let n = 1, so [pic]. Both of these are correct, so the hypothesis holds for [pic]. Now assume that the hypothesis holds for all[pic], so:

[pic],

[pic]

(we are assuming that these are correct)

Using the definition of a recursive sequence we gather:

[pic][pic]

[pic]

[pic]

[pic]

[pic]

[pic]

So the hypothesis holds for [pic] and by the PMI for all[pic].

Work In Progress

Bibliography

[1] Benjamin, Arthur T., and Jennifer J. Quinn. Proofs That Really Count: The Art of Combinatorial Proof. United States of America: The Mathematical Association of America, 2003. 1-16.

[2] Bridger, Clyde A. "Leonardo, His Rabbits, and Other Curiosa." The Two-Year College Mathematics Journal 6.1 (1975): 14-20.

[3] Eggen, Maurice, Douglas Smith, and Richard St. Andre. A Transition to Advanced Mathematics. 5th ed. United States: Brooks/Cole, 2001. 106.

[4] Garland, Trudi Hammel. Fascinating Fibonaccis: Mystery and Magic in Numbers. New Jersey: Dale Seymour Publications, 1987. 1-95.

[5] Hendel, Russell Jay. "Approaches to the Formula for the nth Fibonacci Number." The College Mathematics Journal 25.2 (1994): 139-142.

[6] Horadam, A F. "A Generalized Fibonacci Sequence." The American Mathematical Monthly 68.5 (1961): 455-459.

[7] Horadam, A F. "Eight hundred years young." The Australian Mathematics Teacher 31. (1975): 123-134.

[8] Karpinski, Louis C. "Algebra." Modern Language Notes 28.3 (1913)

[9] Katz, Victor J. A History of Mathematics: An Introduction. 2nd ed. Massachusetts: Addison Wesley Longman, Inc., 1998. 307-310.

[10] Knott, Dr Ron. Who Was Fibonacci? 1996. University of Surrey, Dept. of Mathematics and Statistics. Mar. 2005 .

[11] Koshy, Thomas. Fibonacci and Lucas Numbers With Applications. New York: John Wiley & Sons, Inc., 2001. 1-196.

[12] Lovasz, L, J Pelikan, and K Vesztergombi. Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag, 2003. 65-124.

[13] O'Connor, J J., and E F. Robertson. Leonardo Pisano Fibonacci. Oct. 1998. Mac Tutor History of Mathematics Archives. Mar. 2005 .

[14] Renault, Marc. Properties of the Fibonacci Sequence Under Various Moduli. 1996. Wake Forest University. Apr. 2005 .

[15] Roberts, Andrew. Time line for the history of science and social science. Mar. 1999. Middlesex University . Apr. 2005 .

[16] The Golden Mean. The NeWeb Group. Apr. 2005 .

[17] The Fibonacci Sequence . 2004. Math Academy Online. Apr. 2005 .

-----------------------

[1] Horadam

[2] bartleby

[3] Horadam

[4] timeline

[5] Knott

[6] JJ O’Connor

[7] Knott

[8] JJ O’Connor

[9] “Rabbit Problem” as represented in Fibonacci’s Liber Abaci translated into English for the first time by L E Sigler (2002), and reproduced in [10]

[10] Modern notation of the Fibonacci sequence is: 0,1,1,2,3,5,8,13,21…[7]

-----------------------

[pic]

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

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download