Fibonacci's Rabbits

In the West, the Fibonacci sequence first appears in the book Liber Abaci (1202) by Leonardo of Pisa, known as Fibonacci. Fibonacci considers the growth of an idealized (biologically unrealistic) rabbit population, assuming that:

  1. a single newly born pair of rabbits (one male, one female) are put in a field;
  2. rabbits are able to mate at the age of one month so that at the end of its second month a female can produce another pair of rabbits;
  3. rabbits never die and a mating pair always produces one new pair (one male, one female) every month from the second month on.
The puzzle that Fibonacci posed was: how many pairs will there be in one year?


Suppose we let the number of rabbit pairs in the field at the end of the $n^{\text{th}}$ month be denoted by $F_n$.

Consider just the new "baby rabbit pairs" in the $n^{\text{th}}$ month. They must be equal in number to the pairs of rabbits that are mature enough to give birth to baby rabbits. This, of course, is precisely the number of rabbit pairs alive two months previously, $F_{n-2}$.

Now the total number of rabbit pairs in the $n^{\text{th}}$ month is the number of pairs alive in the previous month (i.e., $F_{n-1}$) plus the number of new baby rabbit pairs, $F_{n-2}$.

Thus, we have the following recursive definition for the $n^{\text{th}}$ Fibonacci number, $$F_0 = F_1 = 1$$ $$F_n := F_{n-1} + F_{n-2}$$