Example: The Fibonacci Numbers
One of the earlier examples of a recursively defined sequence
arises in the writings of Fibonacci, who was the greatest
European mathematican of the Middle Ages. In 1202, Fibonacci
posed the following problem.
A single pair of rabbits (male or female) is born at the
beginning of a year. Assume the following conditions:
- Rabbit pairs are not fertile during their first month of life
but thereafter give birth to one new male/female pair at the end
of every month;
- No deaths occur during the year.
How many rabbits will there be at the end of the year ?
Solution:
Let Fn be the number of rabbit pairs alive at the end of month
n.
It is easy to check that F0 = 1, the initial number of rabbit
pairs.
We note that the number of rabbit pairs at the end of month k
is equal to the sum of the number of rabbit pairs at the end of
month k-1 and the number of rabbit pairs born at the end of
month k. We remark that the number of rabbit pairs born at the end
of month k is equal to the number of rabbit pairs at the end
of month k-2.
Therefore, the recurrence relation is given by
To answer Fibonacci's question, it is equal to F12 = 233.
| 
