Fibonacci

Leonardo di Pisa, alias Fibonacci (son of Bonaccio)

lived in the 12^th and 13^th century. He is famous for the sequence of numbers that goes by his name. That (infinite) sequence starts with





The characteristic of this sequence is that each number is the sum of the previous two.
In other words, if we denote the n^th number by F_n, then



F_n+2 = F_n+1 + F_n


The sequence is the solution of a problem which Fibonacci posed in the year 1202:(Click here!) A farmer buys two young rabbits at the marketplace in Pisa: a male and a female. The first month this couple does not produce little ones, but after the second month the first two rabbits are born: a male and a female. At the end of each month of the following months this first couple brings into the world two rabbits, one of each genus. Newborn rabbits start to mate after two months and give birth to a couple of little ones each month. The Fibonacci sequence shows how many rabbits the farmer has in the successive months. We suppose that the rabbits never die. (proof). (Here is another version of this problem).





This problem reveals an unrealistic genealogy. A realistic genealogy in which the Fibonacci sequence shows up is the genealogy of the drones (male bees). A male bee has no father. Fertiliation causes always female bees. So, a male bee has 1 mother and 2 grandparents and 3 great-grandparents (because the male grandparent has no father). Notice the Fibonacci numbers 1,1,2,3,5,... .


Another elegant problem that generates the Fibonacci sequence is:

I want to construct a stone path. To that end I have at my disposal two kinds of stones. Square stones (size 1x1) and rectangular stones (size 1x2). The path width is equal to the width of a 1x1 stone. How many different paths (patterns) of length n can be constructed with these two kinds of stones?

At the top of this page you see a path of length 8 with 4 1x1 stones and 2 1x2 stones.

The answer is F_n+1, which is easy to prove:
Let us denote the number of paths of length k by a_k for each positive integer k. The last stone of a path of length n exists of a 1x1 stone or a 1x2 stone. In case of a 1x1 stone, the rest of the path may be constructed in a_n-1 ways, in case of a 1x2 stone, the rest may be constructed in a_n-2 ways. Thus the path of length n may be constructed in a_n-1 + a_n-2 ways. According to the definition of a_n the number of paths of length n is a_n.
Apparently a_n-1 + a_n-2 = a_n. Now it is an easy exercise to show that a_n = F_n+1 for each n. (See also: Three different approaches).
An alternative variant is:

I want to construct a path with stones of size 1x2. The width of the path is equal to the longest size of a 1x2 stone. How many different paths of length n can I construct with these stones?

Paths of length 1, 2 and 3:


and with length 4

and with length 5


Notice the Fibonacci sequence 1, 2, 3, 5, 8, 13, 21, ...
For the proof we point out, that if we cut through the paths lengthwise, there arises two identical paths with width 1, thus of the type as discussed in the previous problem.