O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 2

The Problem of the Rabbits

In the now famous “Problem of the Rabbits,” Leonardo introduces us to a person who has a pair of newborn rabbits—one of each gender. We are interested in determining the number of pairs of rabbits that can be bred from (and include) this initial pair in a year if

1. each newborn pair, a female and a male, matures in one month and then starts to breed;

2. two months after their birth, and every month thereafter, a now mature pair breed at the beginning of each month. This breeding then results in the birth of one (newborn) pair, a female and a male, at the end of that month; and,

3. no rabbits die during the course of the year.

If we start to examine this situation on the first day of a calendar year, we find the results in Table 2.1 on p. 6.

Table 2.1

img

We need to remember that at the end of each month, a newborn pair (born at the end of the month) grows to maturity, regardless of the number of days—be it 28, 30, or 31—in the next month. This makes the new maturity entry equal to the sum of the prior maturity entry plus the prior newborn entry. Also, since each mature pair produces a newborn pair at the end of that month, the newborn entry for any given month equals the mature entry for the prior month. From the third column in Table 2.1, we see that at the end of the year, the person who started with this one pair of newborn rabbits now has ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required