Wednesday, January 9, 2013

Fibonacci numbers

Leonardo of Pisa, known more commonly as Fibonacci, was born in about 1170 and died in 1240. He is considered the greatest mathematician of the Middle Ages in Europe. He greatest lasting contribution is his book Liber Abaci, where he recommended the use of the number system he called The Arab numerals (now known as Hindu-Arabic numbers, the ones we use today) instead of the Roman numerals still used in Europe in his day. But his name survives because of a math puzzle he created, and the series of numbers that answer the puzzle are still called the Fibonacci numbers.

The puzzle went as follows. You have a pair of rabbits. Their breeding cycle is one month. The original pair gives birth to a new pair. The newborn rabbits are too young to breed, but the original pair will produce another pair of rabbits in the next month and the newborn will grow to maturity in a month so they will start breeding. How many pair of rabbits will you have in a year?

Of course, rabbits don't actually breed this way, but let's solve the problem anyway

Beginning of January: 1 pair
Beginning of February: 2 pairs, only 1 fertile
Beginning of March: 3 pairs, only 2 fertile
Beginning of April: 5 pairs, 3 fertile
Beginning of May: 8 pairs, 5 fertile
Beginning of June: 13 pairs, 8 fertile
Beginning of July: 21 pairs, 13 fertile
Beginning of August: 34 pairs, 21 fertile
Beginning of September: 55 pairs, 34 fertile
Beginning of October: 89 pairs, 55 fertile
Beginning of November: 144 pairs, 89 fertile
Beginning of December: 233 pairs, 144 fertile
Beginning of next January: 377 pairs, 233 fertile

This is the beginning of the sequence called the Fibonacci numbers. As you can see, the number of fertile rabbits follows the same pattern as the number of rabbits, just a month behind.

The rule that creates the Fibonacci numbers: The next Fibonacci number is always the sum of the previous two Fibonacci numbers.

The modern way to count them:  In number theory today, instead of starting with 1 and 2, the Fibonacci sequence starts with 0 and 1. We can write them this way.

f0 = 0
f1 = 1
f2 = 0+1 = 1
f3 = 1+1 = 2
f4 = 1+2 = 3
f5 = 2+3 = 5
f6 = 3+5 = 8

When speaking, I would say "f 6 equals 8" or "the sixth Fibonacci number is 8". There are some interesting number theory patterns in the sequence dealing with divisibility.

Rule: Any two consecutive positive Fibonacci numbers are relatively prime.
Rule: The fifth Fibonacci number is 5, and every fifth number in the sequence is divisible by 5.
f10 = 55 and f15 = 233 + 377 = 610. To test it out for yourself, continue the pattern to find f20 and f25.

The answers are in the comments.

Tomorrow: The Fibonacci sequence shows up in nature.

1 comment:

  1. Following the pattern from 377 and 610

    the 15th: 610
    the 16th: 987
    the 17th: 1,597
    the 18th: 2,584
    the 19th: 4,181
    the 20th: 6,765
    the 21st: 10,946
    the 22nd: 17,711
    the 23rd: 28,657
    the 24th: 46,368
    the 25th: 75,025

    You can prove this by looking at the sequence, dividing by 5 and taking the remainders. Then we get, starting from 0

    0, 1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, ...

    Every fifth number in this sequence is 0. When the remainder in division is 0, that means the number is divisible exactly by whatever number you were dividing by, in this case 5.