## Monday, September 27, 2010

### Introduction to Fibonacci numbers

I plan on writing a few posts about Fibonacci numbers over the next few days simply because I think they're neat and interesting.

Fibonacci numbers are named after Leonardo of Pisa (c. 1170 - c. 1250), later known as Fibonacci (an name attributed to him from the contraction of filius Bonacci or "son of Bonaccio").

Fibonacci was one of the premier mathematicians of his day.  His Italian merchant father was a diplomat staioned in Bugia in what's now Algeria in North Africa and Fibonacci was able to travel with him around the Mediterranean world.

In 1202, Fibonacci wrote Liber Abaci which means "Book of the Abacus" or "Book of Calculation." In it, he introduced the European world to the Hindu-Arabic number notation.  This was a huge advance for western mathematics (try doing math with Roman numerals!).

When my father, who had been appointed by his country as public notary in the customs at Bugia acting for the Pisan merchants going there, was in charge, he summoned me to him while I was still a child, and having an eye to usefulness and future convenience, desired me to stay there and receive instruction in the school of accounting. There, when I had been introduced to the art of the Indians' nine symbols through remarkable teaching, knowledge of the art very soon pleased me above all else and I came to understand it, for whatever was studied by the art in Egypt, Syria, Greece, Sicily and Provence, in all its various forms.

European merchants quickly saw the advantage of the new Arabic numerals which greatly simplified bookkeeping chores.  This new system of notation also led to advances in mathematics which suddenly became much easier with the improved notational system.

In Liber Abaci, Fibonacci proposed a hypothetical problem whose answer has intrigued people for almost a millennium now.  It has to do with rabbits (you know the stereotype about rabbits, right?).  Assume rabbits can mate at one month of age and at the end of the seconds month have a litter of two rabbits - one male and one female.  Rabbits never die and each month, from the second month on, keep producing a new pair of male and female rabbits.  Unrealistic, but it's a hypothetical problem, we're allowed to set whatever conditions we like.

So, let's start with a pair of bunnies.  How many rabbits will there be at the end of each month?  Check out the figure below.  Pink and blue for female and male bunnies, lighter colors for sexually immature and darker colors for mature (takes 1 month to mature).

For the first month, we only have the original pair of immature bunnies.  In the second month, the bunnies are now mature and hook up as nature intended.  In the third month, the original pair has an offspring pair which are immature.  In the fourth month, the original pair has another pair of offspring the the two mature pairs (original pair and first generation pair) have sex.  In the fifth generation, the first pair has a second pair of offspring and the 1st generation pair has its own offspring.  The two pair of offspring are immature.

And so on.

Note the progression in the number of pairs with each generation: 1, 1, 2, 3, and 5.  If you continue this for a year, you'll see the sequence:  1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and 144.  After one year, you'll have 144 pairs of bunnies.  Looking at the sequence, it's obvious that each number is the sum of the two previous numbers (after we start with 1).  This is called the Fibonacci sequence and its more formal definition is:

F1 = 1, F2 = 1, and Fn = Fn-1 + Fn-2

Using this notation F13 = 233 since F13-1 = F12 = 144 and F13-2 = F11 = 89 and 144 + 89 = 233.

Fibonacci numbers obviously form an infinite sequence because given any Fn, we can always generate Fn+1 from Fn + Fn-1.

Why is this so interesting?  Who the hell cares about bunny sex besides rabbits?  I'll post some interesting things about the sequence over the next few days but here's one thing...

The ratio of any two successive Fibonacci numbers (Fn / Fn-1) approaches a constant with successively larger pairs.  For example:

F2 / F1 = 1/1 = 1.000000
F3 / F2 = 2/1 = 0.500000
F4 / F3 = 3/2 = 1.500000
F5 / F4 = 5/3 = 1.666667
F6 / F5 = 8/5 = 1.600000
F7 / F6 = 13/8 = 1.625000
...
F12/F11 = 144/89 = 1.617977528090
...
F24 / F23 = 28,657/17,711 = 1.618033990176
...
F48 / F47 =  4,807,526,976/2,971,215,073 = 1.618033988750

And so forth.  The number approached is an irrational number (an infinite non-repeating decimal) designated by the Greek letter Phi (F).  It's value (to 18 decimal places) is 1.618033988749894848… but realize it goes on forever and the higher you go in the Fibonacci sequence, the more closely you'll approach it.

This special number was called Phi (pronounced "fie" or "fee") after Phidias (Φειδίας) an ancient Greek artist who lived circa 480-430 BCE (his 12 meter high statue of Zeus at Olympia was one of the Seven Wonders of the Ancient World).  The reason for this will wait until another post.