What's up with Fibonacci numbers?
Dear Straight Dope:
What is the deal with Fibonacci numbers? What are they? Why are they important?
Cecil this week is dealing with what Fibonacci numbers (and the related number phi) aren't. I'll try to give you some indication what they are.
One of the occasional gags in old cartoons was a reference to "multiplying like bunnies," followed by a cut to a pair of bunnies reciting their times tables. If Chuck Jones had taken more math, they might be reading off the Fibonacci sequence instead.
Leonardo Pisano's father was nicknamed "Bonacci" for his simple nature, and Leo got stuck with "filius Bonacci" (son of Bonacci) or Fibonacci, since Simpson was copyrighted. He studied under Arabic mathematicians in his youth and in 1202, at the tender age of 27, published Liber Abaci, or Book of Calculation, which applied the newfangled (to Europe) positional base-10 system to commercial bookkeeping.
Also around this time, he tried to determine how fast a population of rabbits grew. In the time-honored tradition of mathematicians, he made some pretty wild assumptions: We start with one pair of newborn bunnies. Pairs of bunnies become sexually mature at 2 months. Each month, each sexually mature pair begets a new pair. Annoying problems like inbreeding and pairs not mating for life don't exist. Bunnies never die.
Now, let's say in month n we have Fn pairs. Next month we'll have all of these bunnies (since they never die) plus one new pair for each pair that was born at least a month ago (from all the pairs that will be mature by next month). This means that Fn+1 = Fn+Fn-1. Starting with F1 = F2 = 1 (since we started with a single pair and they don't reproduce until their second month), we get the famous Fibonacci sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 . . .
Each number in the sequence is the sum of the two preceding numbers. This sequence increases almost exponentially--that is, almost in the form bn for some b. Fn+1/Fn converges to the value phi as n increases. Phi is the "golden ratio" (1+sqrt(5))/2, which has many interesting properties related to scaling and self-similarity. Logarithmic spirals, for instance, are the same when rotated a quarter turn and scaled down by a factor of phi. Spirals show up everywhere in nature, since they're a good way to pack a lot of volume in a small space and allow room to grow. A lot of structures in nature, from pine cones and sunflowers to nautilus shells, are related to Fibonacci's sequence.
Another place Fibonacci's sequence come up a lot is in chaos theory, that is, the study of chaotic dynamical systems. One tool in chaos theory is the "cat map," in which an algorithm is used to transform a matrix in seemingly chaotic ways. (One early matrix was a graphic of a cat, hence the name.) The "cat map" is transformed by starting with two numbers x and y between 0 and 1, sending the pair (x, y) to (2x+y, x+y), and throwing away the integer parts of the resulting numbers to get another pair between 0 and 1. Lather, rinse, repeat, and you'll find that the coefficients always come from the Fibonacci sequence:
(x, y) -> (2x+y, x+y) -> (5x+3y, 3x+2y) -> (13x+8y, 8x+5y) -> . . .
One of the hallmarks of chaos theory is that many systems look very similar, so many dynamical systems have structures similar to that of the cat map. Whether the exact Fibonacci sequence is part of that structure of just a consequence of the simplicity of this model example is pretty open, but most mathematicians would chalk it up to chance. Then again, if you can find a connection there could well be a Fields medal in it for you.
If you want to play around with these sequences and learn more on your own, I highly recommend Mathematical Reflections: In a Room with Many Mirrors (Hilton et al, 1996). It explains a lot about why the Fibonacci sequence has the properties it does, but is accessible to anyone who got through high school math and is willing to roll up their sleeves and do a bit more.