Numbers: Fibonacci Numbers/ ...

It is interesting that among the numbers of petals of flowers, the numbers 3, 5, 8, 13, 21, 34, 55, or 89 occur over and over. Here are some examples:

Some of these numbers also occur as numbers of spirals in seedheads or pinecones.

In pre-enlightenment time, these numbers 5, 8, 13, 21, 34, 55, 89, ... might have been considered as "holy numbers", if somebody would have counted the petals and spirals, which apparently nobody bothered to do. On the other hand, other numbers were considered holy and "supernatural", since they seemed to rule nature. Of course (?) nowadays we try to find a cause if patterns occur in nature. In this case, the cause is difficult to detect, only around 1990 biologists found the reason for it in case of spirals in seedheads.

The sequence of numbers 1, 1, 2, 3, 5, 8, 13, 21, ... was described by the mathematicican Leonardo da Pisa, whose nickname was Fibonacci (the son of Bonacci). Actually Fibonacci illustrated the numbers using an example of rabbits reproducing themselves. He lived around 1180-1241 in Pisa, and is considered to have been the most famous European mathematician of the middle ages (although Arabic, Indian and Chinese mathematicians of that time were more famous). He was one of the first europeans using the indian-arabic ten digits. For this reason, these numbers are called "Fibonacci numbers". However, according to some sources, the Indian mathematician Pingala described and used these numbers already around 400BC.

The Fibonacci numbers F1, F2, F3, ... can be described by following the rule Fn+2 = Fn+1 + Fn. In other words: Every number of the sequence (except the first two, of course, which are just defined to be 1 and 1) is the sum of the two previous numbers in the sequence.

In the following applet you can generate larger and larger Fibonacci numbers:
n
Fn Fn+1 Fn+2
+ =
Fn+1/Fn

Why Fibonacci Numbers and the Golden Ratio occur in seedheads

In the following applet you can generate a pinecone or a sunflower seedhead. Write a number into the "number of seeds" field. type a number between 0 and 1 into the "angle as part of 360" field. Then click the "Read and Do" button, or the "step" button repeatedly if you want to create the pinecone step by step. The pinecone is created by placing a new seed close to the center, and then more seeds going counterclockwise and increasing the distance from the center more and more. Note that you see only one set of spirals, and the pattern doesn't look like in nature, unless you use the number close to 0.61803399 as angle ratio. Only in these case the seeds are very closely packed, you see two sets of spirals, one clockwise and one counterclockwise, and it looks like in Nature. So what is so special about the number 0.61803399?

How many trains?

Fibonacci numbers do not only occur in nature, but many natural questions lead to Fibonacci numbers as answers. Here is an example:

Assume you have two types of train cars---those of length 1 and those of length 2. Let's abbreviate those of length 1 by the letter "a" and those of length 2 by the letter "w". Then "awa", "waa", "aww", "ww", and "aaaa" are the five possible trains of length 4. Note that two such trains are only considered equal if both have the same cards in the same ordering from left to right. Now there are the eight trains "wwa", "waw", "aww", "waaa", "awaa", "aawa", "aaaw", "aaaaa" of length 5, and the 13 trains "www", "wwaa", "wawa", ""waaw", "awwa", "awaw", "aaww", "waaaa", "awaaa", "aawaa", "aaawa", "aaaaw", "aaaaaa" of length 6. This data may indicate the conjecture that there are Fn trains of length n.

Theorem: There are Fn trains of length n, for every natural number n.

We will use a different proof technique than that (Reductio ad Absurdum) we used last time. The new method is called "Mathematical Induction".

First we will show that the statement is true for small cases of n. Actually this has already been showed above.

The next step, the induction step, consists in showing that if the statement we have to proof is valid for all numbers less than a given number n, then it must also be true for that n.

In our case, the key observation is that there are two types of trains: Those whose\ first car has length 1, let's call them "type-1", and those whose first train has length 2, the "type-2" trains.

Now how many type-1 trains of length n do we have? Well, as many as there are length n-1 trains, since there are n-1 units to be combined after the leading (length 1) car. By the assumption, this number equals Fn-1.

In the same way, the number of type-2 trains of length n equals the number of trains of length n-2, which equals by our assumption Fn-2.

Every train obviously has one (and only one type). Therefore the number of length n trains equals the sum of the number of length n trains of type-1 and type-2, which is Fn-1+Fn+2. But according to the recurrence formula for Fibonacci numbers, this equals Fn, and the proof is complete.

This question, using long and short syllables instead of cars, and words instead of trains, was raised and answered by the Indian mathematician Virahanka around 600BC.

The Golden Ratio

Look into ratios of consecutive Fibonacci numbers (just click several times on the button above to create these ratios) 3/2=1.5, 5/3=1.666, 8/5=1.6, 13/8=1.625, 21/13=1.6153, 34/21=1.6190, ... Note that after 20 clicks these ratios more or less stabilize. The resulting number is called F, and is called the "golden ratio".

F can be computed: Express these ratios as compound fractions. Let Rn be the ratio of Rn and Rn-1:
       
In general:

Using the method of mathematical induction, there follows that every such ratio of consecutive Fibonacci numbers has the form Rn = 1+1/(1+1/(1+1/(1+1/...(1+1/1)))). (At this point, there was a brief discussion of inductive versus deductive method in science and in mathematics.)

Then F = 1+1/F. Using a little algebra and quadratic equation, there follows that F = (1+sqrt(5))/2 , which is about 1.6190

This result, that the ratios of consecutive Fibonacci numbers approach the golden ratio has been found by Johannes Kepler in 1619.

Binet's Formula

If we know that the ratio of consecutive Fibonacci numbers equals about F, then we also know that the Fibonacci sequence is about a geometric series, like 1, F, F2, F3, ...


Further Reading:

Exercises

  1. Look at the expressions Fn+1·Fn-1-Fn2. For instance, for n=2 we have 2·1-12=1, for n=3 we have 3·1-22=-1, for n=7 we get 21·8-132=168-169=-1. Is there a pattern?
  2. Look at the sum of squares of consecutive Fibonacci numbers, like 32+52=9+25=34, or 52+82=25+64=89. What do you observe about the result?
  3. Divide each of the first 24 Fibonacci numbers by 4 and list their remainders in a table. What observations can you make? Repeat by dividing the first 30 Fibonacci numbers by 9 and list their remainders. Are there similar observations that can be made?
  4. a) Find GCD(233,377).
    b) Show that for every two consecutive Fibonacci numbers Fn and Fn+1, GCD(Fn,Fn)=1. (Hint: What would Euclid's algorithm output if you put Fn and Fn+1 in?
  5. a) Find GCD(144,377).
    Show that for every two consecutive Fibonacci numbers Fn and Fn+2, GCD(Fn,Fn)=2.
  6. Define numbers Tn recursively as follows: T1=1, T2=1, T3=2, and Tn+3=Tn+Tn+2 for all n > 3. Find T30

Possible Projects:

  1. Assume there are two types of cars: Those of length 1 and those of length 3. How many trains of total length 30 are possible? Give a general formula of how many trains of length n are possible.
  2. Assume there are two types of cars: Those of length 2 and those of length 3. How many trains of total length 30 are possible? Give a general formula of how many trains of length n are possible.