In 1202, Leonardo of Pisa (commonly known as Fibonacci) considered a mathematical exercise regarding the reproduction of a population of rabbits. He made the following simplifying assumptions about the population:
- The population begins in the first month with a pair of newborn rabbits.
- Rabbits reach reproductive age after one month.
- In any given month, every rabbit of reproductive age mates with another rabbit of reproductive age.
- Exactly one month after two rabbits mate, they produce one male and one female rabbit.
- Rabbits never die or stop reproducing.
Fibonacci's exercise was to calculate how many pairs of rabbits would remain in one year. We can see that in the second month, the first pair of rabbits reach reproductive age and mate. In the third month, another pair of rabbits is born, and we have two rabbit pairs; our first pair of rabbits mates again. In the fourth month, another pair of rabbits is born to the original pair, while the second pair reach maturity and mate (with three total pairs). The dynamics of the rabbit population are illustrated in Figure 1. After a year, the rabbit population boasts 144 pairs.
Although Fibonacci's assumption of the rabbits' immortality may seem a bit farfetched, his model was not unrealistic for reproduction in a predator-free environment: European rabbits were introduced to Australia in the mid 19th Century, a place with no real indigenous predators for them. Within 50 years, the rabbits had already eradicated many plant species across the continent, leading to irreversible changes in the Australian ecosystem and turning much of its grasslands into eroded, practically uninhabitable parts of the modern Outback (see Figure 2). In this problem, we will use the simple idea of counting rabbits to introduce a new computational topic, which involves building up large solutions from smaller ones.
A sequence is an ordered collection of objects (usually numbers), which are allowed to repeat. Sequences can be finite or infinite.
Two examples are the finite sequence
A recurrence relation is a way of defining the terms of a sequence with respect to the values
of previous terms. In the case of Fibonacci's rabbits from the introduction, any given
month will contain the rabbits that were alive the previous month, plus any new offspring.
A key observation is that the number of offspring in any month is equal to the number of
rabbits that were alive two months prior. As a result, if
When finding the
Given: Positive integers
Return: The total number of rabbit pairs that will be present after