# Fibonacci Sequence

This is an excerpt from Master Fibonacci: The Man Who Changed Math. All citations are catalogued on the Citations page.

### WHAT IS THE FIBONACCI SEQUENCE?

#### 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 . . .

(Previous Section: Fibonacci’s Intellectual Legacy)

Leonardo Pisano, or ‘Fibonacci,’ was a self-professed student of the arts of Greek theologian and mathematician Pythagoras (c. 569 – 475 BCE), who coined the term ‘mathematics’ (Μάθημα, ατος, τo, that which is learned) to represent that abstract science which studies shape, quantity, and space (Donnegan 26). Pythagoras was primarily interested in number theories and their application to music rather than the use of numbers for everyday computation (O’Shea). Greek mathematician Euclid also greatly influenced Fibonacci; as highlighted previously, his thirteen books (chapters) on geometry in Elements (c. 300 BCE) provided definitions, postulates and axioms of geometry which Fibonacci knew well. Elements is considered by many the most scientifically significant mathematical work until the 20th century (“Euclid”). “Even today a large part of mathematical and geometrical elementary education is based on the Euclidean tradition” (“Euclid”).

Long before Pythagoras or Euclid, man recorded counting by “scratching tally marks on a stick or bone” (Devlin, Man 13). Mathematics has evolved greatly since then; today, math equations are so inconspicuously calculated by computers that most people tend to think about mathematics “only in the day-to-day context in which they themselves are immersed” (Radford).

One of the earliest proofs of math skills practice is a papyrus written by an Egyptian scribe named Ahmes (∼1650 BCE), who recorded a “series of 87 exercises and problems, presumably for students to try with the assistance and guidance of a teacher” (Levy 21).

The concept of “nothing” in math may have been represented first by a dot to indicate an empty placeholder, but zero was first used as a number in the seventh century (rather than as a mere concept) by the Indian mathematician and astronomer Brahmagupta, who also devised rules for its use as a number (Levy 93). Because the idea of nothing was important in early Indian religion and philosophy, it was much more natural for them to adopt a symbol for it than it was for the Latin (Roman) and Greek systems (Knott, “Brief”). Thus, zero was used in India for addition, subtraction, and multiplication but not division; the concept of dividing something by “nothing” was too difficult for even the brilliant Brahmagupta (Levy 93).

Islamic mathematicians in Egypt, such as Abu Kamil (c. 850 – c. 930 CE), produced important but “only incremental progress” in the development of algebra, particularly of the use of the Golden Ratio (Sesiano). Such incremental advancement may not have been revolutionary, but it was necessary for the preparation of later mathematicians (like Fibonacci) to push forward the next major math breakthrough (Livio 91).

Suleimān the Merchant, a well-known Arab trader of the ninth century, may have introduced the Hindu-Arabic symbols (including the numeral zero) to European markets, and “Abū ‘l-Ḥasan ‛Alī al-Mas‛ūdī (d. 956 CE) of Baghdad traveled to the China Sea on the east, as far south as Zanzibar, and to the Atlantic on the west; he speaks of the nine figures with which the Hindus reckoned (Smith and Karpinski). Thus, Islamic mathematicians may have learned the number zero from India but “failed to make use of it in algebra.” Hundreds of years later, Fibonacci did not consider zero a number like other numerals, either; instead, he referred to it as a symbol in his book Liber Abaci (Levy 93).

Educated and (of course) fluent in Latin, Fibonacci studied al- Khwarizmi’s compendium of rules for calculating Hindu- Arabic arithmetic in a book which was later translated into Latin and given the title, Algoritmi de Numero Indorum (Concerning the Hindu Art of Reckoning) (Devlin, Man 24). First exposed to this book either in Bugia or perhaps while traveling the Mediterranean, it greatly influenced Fibonacci’s understanding and practice of the Hindu-Arabic arithmetic.

Although Kamil and al-Khwarizmi were accomplished mathematicians in the Arabic world and some in Europe were aware of their arithmetic strategies, a commercial revolution did not emerge from Baghdad at that time because Western commercialism “had not yet developed sufficiently for the new methods to have widespread impact” (Devlin, Finding 32).

In fact, early in the twelfth century, other books explaining the Hindu art of reckoning were written but the new numerals were not enthusiastically embraced. Slowly, however, Italian merchants and bankers who initially opposed the unfamiliar numerals and the new calculation methods eventually understood its advantages over the traditional method of using Roman numerals. Transitioning to the new math, for example, eliminated the need of counting boards and other primitive means of commerce and banking. Among these was the primitive use of tally sticks; the money value of a loan was written upon a tally stick which was split in two. The lender kept the biggest piece – the stock – becoming the “stockholder” (Seife 81).

Society was reluctant to adopt the Hindu-Arabic arithmetic system for many reasons, only a few of which will be mentioned here. Perhaps the most significant is the natural human aversion to change. Roman numerals had worked well enough with ancient counting devices and abaci for millennia; they had met the need for addition, subtraction, and multiplication. Moreover, little explanation was required to successfully operate an abacus (extensive practice was needed to truly excel in its use, however, especially when multiplying different orders of numbers) (Smith and Karpinski).

Another reason is that social discord between abacists (the advocates of the abacus) and algorists (those who favored the use of the Hindu-Arabic numerals) kept the newer, more efficient system from becoming universally adopted by European society for years. In fact, “merchants’ ledgers featured Roman numerals throughout the Middle Ages, indicating that [some] remained staunchly abaci” (Levy 117).

Newly-established universities were sometimes antagonistic toward algorism but a more powerful impediment to the dissemination of the Hindu-Arabic math method was civil authority. At the end of the 13th century, the use of new numbers was forbidden by local governments in several Italian cities. Florence in 1299, for example, passed statutes forbidding moneychangers’ guilds (bankers) from using Arabic numerals (Levy 117). Similarly, the statutes of the University of Padua required stationers to keep the price lists of books “non per cifras, sed per literas claros” (loosely translated, “not in numbers but clearly in letters”) (Smith and Karpinski). This was in large part because written numbers could be easily changed or forged; a simple flourish of a pen could transform a zero into a 6 or a 9, for instance. Roman numerals were not so easily altered; 10 is represented by the letter X, for example. Bankers recorded money orders in words, therefore, which is a practice we still utilize when writing checks today (Ghusayni 84).

Fibonacci recognized the advantages of zero and the other Arabic numerals; he knew that the benefits far outweighed the hazards. Italian merchants who agreed with him continued to use them, too, even when forbidden (Seife 81). In addition, the spread of a cashless trade society (through the issuing of bills of exchange and checks), and the growth of interest calculation compelled banks to quite pragmatically accept the new method of calculation pushed by Fibonacci. In the end, governments relented to commercial pressure and the Arabic notation flourished in Italy and soon spread throughout Europe (Seife 81).

#### CONTESA DI MATEMATICA: ABACISTS VS. ALGORISTS

The abacists (sometimes spelled abakists) were people who preferred to use the traditional Roman numerals and mechanical tools (abaci, boards, or checker- patterned cloths) to perform arithmetic, and algorists were people who embraced the written, symbolic Hindu-Arabic notation of place-value (including the zero) and calculated using algorithmic methods or formulas (Levy 112). Most algorists renounced the use of the abacus.

An illustration in philosopher Gregor Reisch’s book, Margarita Philosophica (Pearl of Wisdom) (1503) portrays the struggle between traditional and modern methods of arithmetic. The woodcut engraving, titled “The Allegory of Arithmetic,” depicts a competition of sorts between those who favored Roman numeration and clung to tradition (use of the abacus) and those who had adopted the algorithmic method and calculated on pen and paper. Banners labeled “Boetius” and “Pythagoras” identify the men in the picture. The ancient Greek scholar Pythagoras (c. 500 BCE) is shown on the right in the illustration with a worried frown, using a counting board; he represents abakists. On the left, Roman philosopher Boethius (c. 500 CE) appears to be happy as he uses Indian-Arabic numerals, representing algorists (“Fibonacci” Famous; “Dispute”).

Classic woodcut of Arithmetica (or the Allegory of Arithmetic) supervising a contest between Boëthius, representing written calculation using Hindu-Arabic numbers, and Pythagoras, represented as using a counting board.

Of course, neither of these men were alive during Reisch’s lifetime (1467 – 1525 CE); in fact, roughly 1000 years had passed between the lifetimes of the two ancient philosophers and another 1000 years had passed between Reisch and Boethius! The woodcut picture is anachronistic, belonging to a time other than that which it portrays, and the characters in the scene are symbols, representing ideas. One could say the woodcut is a kind of medieval infographic.

Between the two mathematic opponents hovers the muse of arithmetic, Arithmetica, wearing a dress adorned with the Arabic numerals. Her dress decoration and her favorable look upon the figure of Boethius suggest that, by the end of the fourteenth century, algorismi was becoming increasingly more popular (O’Shea; O’Connor and Robertson). Sometime between 1400 and 1700, it ultimately prevailed.

The adoption of the new math by European economic systems was sluggish to say the least; if it were depicted in a woodcut in Reisch’s book it might be a hobbling tortoise, while the spread of the Hindu-Arabic numerals in academic circles would be a sprinting hare. Fibonacci championed the Hindu-Arabic numeral system of al-Khwarizmi and Kamil in Liber Abaci, which is now regarded as “the seminal work in transmitting to the West the Hindu-Arabic numerals and how to add, subtract, multiply, and divide with them.” Even more influential than the encyclopedic Liber Abaci was his smaller, more accessible digest, the Libro di Minor Guise (Book in a Smaller Manner), which circulated widely among merchants and was copied countless times by motivated traders, merchants, and bankers (Levy 117).

Despite Fibonacci showing how useful Arabic numerals were for performing complex calculations, the printing press had not yet been invented; so, knowledge spread slowly, for the most part, during the Middle Ages. “Popes and princes and even great religious institutions possessed far fewer books than many farmers of the present age” (Smith and Karpinski). Nevertheless, as with most innovations and strategies that make profitability more efficient, the practical applications in Fibonacci’s books could not help but spread like a wildfire in the tinderbox of the market economy which had developed in the Western world.

Some historians have asserted that treatises on algorism by others, such as the Carmen de Algorismo by Alexander de Villa Dei (c. 1240 CE) and the Algorismus Vulgaris by John of Halifax (Sacrobosco, c. 1250 CE) were much more influential and more widely used than Fibonacci’s and “doubtless contributed more to the spread of the numerals among the common people” (Smith and Karpinski; “Transition”). However, more recent research has unearthed hundreds of manuscripts called libri d’abbaco (“abbacus books”) or trattati d’abbaco (“abbacus tracts”) which clearly point to Leonardo’s Liber Abaci as the “gunshot” or “spark that lit the fire of the modern commercial world” in the late Middle Ages “because it was a highly combustible landscape,” already experiencing rapid commercial expansion (Devlin Finding 25, 27, 33).

It may now seem inconceivable that the Western world balked at adopting the new numerals embraced so “stringently” by Leonardo Pisano; they were so obviously superior to calculation methods then prevalent in Christian Europe! In twenty-first century terms, Fibonacci’s Liber Abaci was a new market instrument of disruption because it fit an emerging market segment (international trade) that was underserved by existing tools (Roman numerals and the abacus) in the industry.

Initially, and certainly while he was alive, Fibonacci’s works were intensively studied and appreciated in Italy. Copies of the practical “economic” portions of the book were handwritten and distributed by the thousands, presumably not only by merchants and traders but also by students attending the many Italian vernacular schools which suddenly appeared in the second half of the thirteenth century. Commercial mathematics (abbaco) and complex bookkeeping skills were taught in these schools, in addition to literature. Thus, Liber Abaci significantly influenced not only the great numbers of arithmetic tracts (trattati d’abaco) which were published after Liber Abaci, but also the abbaco schools which flourished in the 14th century (“Education).

#### WHAT ARE FIBONACCI NUMBERS?

The sheer magnitude of the size of Liber Abaci rendered it nearly impossible (certainly impractical) to duplicate in its entirety. The English version of Liber Abaci (a translation begun by American Laurence Sigler and posthumously completed by his wife, Joan), “has more than 600 pages, set in a fairly small typeface; examples are what occupy most of the pages” (Devlin, Finding 88). The book began with explanations and illustrations of how to write and manipulate the Hindu-Arabic numbers, then Fibonacci proceeded to provide the basic mechanics of Hindu-Arabic arithmetic, which he “explain[ed] using (many) specific numerical examples, much like the way elementary school pupils are taught today (Devlin, Finding 116). In succeeding chapters, he supplied real-world examples and demonstrated valuable methods for solving problems specifically relevant to business and companies. The mammoth twelfth chapter contained 259 worked examples (in Sigler’s translation, the chapter fills 187 printed pages) (Devlin, Finding 119).

##### The Rabbit Problem

Found on pages 123-4 of the surviving second edition of 1228 was “a theoretical family of ‘abracadabric’ rabbits conjured up in the mind” of the young, brilliant mathematician (Lines 6, 19). This problem leads to the introduction of the Fibonacci numbers and the Fibonacci sequence for which Leonardo is best remembered today. He presented the following puzzle (paraphrased):

A certain man put a pair of newly-born rabbits, one male, one female, into a garden surrounded by a wall. Rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits. How many pairs of rabbits can be produced from that pair in a year if the rabbits never die and if every month each pair begets a new pair which from the second month on becomes productive? He then explained: “Because the above pair gives birth in the first month, you can double it so that after one month there are two pairs. Of these, one, that is, the first, gives birth in the second month; and so there are three pairs in the second month. Two of them become pregnant again in one month, so that in the third month two pairs of rabbits are born; and so it will be five pairs this month. Of those, three become pregnant in the same month, so there are eight pairs in the fourth month. Of these, five couples bear five pairs again; if you add them to the eight pairs, there are thirteen pairs in the fifth month. Of those, the five couples born this month do not mate in the same month, but the other eight couples become pregnant; and so in the sixth month there are twenty-one pairs. If you add to these the thirteen couples who are born in the seventh month, there will be thirty-four couples this month. If you add to these the twenty-one pairs born in the eighth month, there will be fifty-five pairs this month. If you add to these the thirty-four pairs born in the ninth month, there will be eighty-nine pairs this month. Add to this the fifty-five pairs born in the tenth month and this month will be 144 pairs.

>Adding to these the eighty-nine pairs born in the eleventh month will be 233 pairs this month. And if you finally add to these the 144 pairs that were born last month, there are 377 pairs at the end. And so many couples will have given birth to the above-mentioned couple at the place described at the end of a year”

(“The Rabbit”).

We assume: 1. That a pair of rabbits has a pair of children every year. 2. These children are too young to have children of their own until two years later. 3. Rabbits never die. Eppstein observes that the last assumption is unrealistic but makes the problem simpler: “After we have analyzed the simpler version, we could go back and add an assumption e.g. that rabbits die in ten years, but it wouldn’t change the overall behavior of the problem very much.”

We then express the number of pairs of rabbits as a function of time (measured as a number of years since the start of the experiment) (Eppstein):

F(1) = 1 — we start with one pair F(2) = 1 — they’re too young to have children the first year F(3) = 2 — in the second year, they have a pair of children F(4) = 3 — in the third year, they have another pair F(5) = 5 — we get the first set of grandchildren

The problem yields the ‘Fibonacci sequence’: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 . . .

Fibonacci omitted the first term (1) in Liber Abaci. The recurrence formula for these numbers is: F(0) = 0 F(1) = 1 F(n) = F(n − 1) + F(n − 2) n > 1 . Although Fibonacci only gave the sequence, he obviously knew that the nth number of his sequence was the sum of the two previous numbers (Scotta and Marketos). “This sequence, in which each number is the sum of the two preceding numbers, appears in many different areas of mathematics and science” (O’Connor and Robertson).

Fibonacci probably did not invent the rabbit problem but rather included one he had learned himself from the Moors or while traveling (Knott). He may have even relied on “translations of the works of Al-Khwˆarizmˆı by Gerard of Cremona (1114-1187 CE), the latter being a pioneer in a major effort based in Toledo, Spain, to translate works written in Arabic into Latin for (Christian) Europe” (Scotta and Marketos). The sequence F(n) was already known and discussed by Indian mathematicians “who had long been interested in rhythmic patterns that are formed from one-beat and two-beat notes. The number of such rhythms having n beats altogether is F(n+1). Therefore both Gospala (before 1135) and Hemachandra (c. 1150) mentioned the numbers 1, 2, 3, 5, 8, 13, 21, … explicitly.

“Fibonacci himself does not seem to have associated that much importance to them; the rabbit problem seemed to be a minor exercise within his work” (Scotta and Marketos). It wasn’t until the 19th century that the sequence assumed “major importance and recognition thanks to the work of the French mathematician Edouard Lucas.” Since then, mathematics historians have wondered about the true inspiration behind these numbers and whether Fibonacci was fully aware of their significance (Scotta and Marketos). Though Fibonacci covered a multitude of mathematical topics, he is best known for this number sequence which was later named after him by Guillaume Libri in 1838 and is still to this day being actively researched (“The Rabbit Problem”). While the “Rabbit Problem” is interesting and is the one for which he is most famous today, it is by no means the only significant mathematical problem presented in Liber Abaci. For example, borrowing a scenario from a ninth-century book, Ganita Sara Sangraha, by Mahavira (c. 800-870), Fibonacci presented a series of “purse problems” for the benefit of those who may want to divide money between two or more people. In everyday terms, he clarified the rules to follow for equal and fair distribution of something (such as money). The first solution to the “purse problem” filled half a parchment page and then he provided many more complicated variations of the same problem along with their solutions, including how to distribute the same quantity of money in a purse found by three men rather than two, a purse found by four men, and finally a purse found by five men. Pages later, Fibonacci had included solutions to eighteen different purse problems, each with a “unique twist and each using slightly different numbers.” (Devlin, Finding 121).

#### FIBONACCI’S MATHEMATICAL CONTRIBUTIONS

##### First: Numbers

The place-value system of numeral writing is far easier to work with than the letter-based Roman numeral system; the position of a numeral determines its magnitude in relation to other digits in the number (for example, the 1 in 19, being the second digit in the “tens” place, signifies a value ten times its nominal value or 10 x 1). Fibonacci showed traders and merchants how to use the place- value system of arithmetic.

##### Second: Digits and Decimals

For centuries Europe used the Roman numeral system in which seven symbols represented seven distinct values; the Roman number 2018 could be written as MMXVIII or IIIXVMM – the letter order does not matter since the values of the letters are added to make the number.

I=1 V=5 X=10 L=50 C=100 D=500 M=1000

In the Hindu-Arabic system, the order of the numerals always matters because the position of each digit determines its value; the number 2018 is quite different from 8102. Fibonacci compelled commercial use of the Arabic symbols – 1, 2, 3, 4, 5, 6, 7, 8, 9 – which had been known in Europe but had not been implemented in everyday practice; most importantly, this numeric system included a symbol for zero. Zero is needed as a place-holder because it ensures digits are placed into their proper places (columns); e.g. 2009 has no tens and no hundreds. The Roman system would have written 2009 as MMIX, omitting the values not used. Roman arithmetic was not easy; for example, MXVII added to LI is MLVIII and XLI less IV is XXXVII (Knott, “Brief”). In Liber Abaci (1228), Fibonacci acknowledged studying algorism extensively while traveling on business; back home in Italy, he passionately taught the rules of arithmetic he had learned from Arab mathematicians and provided the first systematic representation of the decimal system in Europe (Knott, “Brief”).

##### Fibonacci and Algebra

While demonstrating his mathematical ability during a presentation to Emperor Frederick’s Pisan court in 1225, Fibonacci explained how he would solve the following Diophantine algebraic problem: Solve x3 + 2×2 + 10x = 20. Recognizing that Euclid’s method of solving equations by square roots would not work, Fibonacci used “an original method of his own, giving his answer in (Babylonian) sexagesimal notation. His approximation was far more accurate than those of his Arab contemporaries” and astounded the audience (Horadam). Soon after this occasion, Fibonacci wrote another brief treatise, Flos (1225) (The Flower, an inexplicable name since it has nothing perceivably to do with flowering plants), explaining how he had arrived at his solution to this algebra problem and another.