In 1202, an Italian merchant and mathematician named Leonardo of Pisa — later nicknamed "Fibonacci," short for filius Bonacci, "son of Bonacci" — published a massive book called Liber Abaci ("The Book of Calculation"). Most of it is about practical arithmetic: converting currencies, calculating profit, using the Hindu-Arabic numeral system (the 0–9 digits you use every day) instead of Roman numerals. Buried in it, though, is a brain teaser about rabbits that turned out to be far more famous than anything else in the book.

Here's the puzzle, slightly modernized. Suppose you start with a single newborn pair of rabbits, one male and one female. Rabbits take one month to mature, and after that, every pair produces a new pair every month. No rabbits ever die. How many pairs of rabbits do you have after one year?

Work through the first few months by hand. In month 1, you have your original immature pair: 1 pair. In month 2, they've matured but haven't yet given birth, so still 1 pair. In month 3, they produce a new pair, giving 2 pairs total. In month 4, the original pair produces another new pair (the pair born in month 3 is still immature), giving 3 pairs. In month 5, both the original pair and the month-3 pair are mature enough to breed, adding 2 new pairs to the existing 3, for 5 pairs total.

Notice what's happening: each month's total is the sum of the two previous months' totals. That's because every pair alive two months ago is now mature and produces a new pair this month, while every pair alive last month simply survives into this month unchanged. Total pairs this month = pairs last month (all of them survive) + pairs two months ago (each of those produces one new pair now).

This relationship — where each term depends on the terms before it — is called a recurrence relation: a rule that defines each term of a sequence using earlier terms in the same sequence. Writing $F_n$ for the number of rabbit pairs in month $n$, the rabbit rule becomes:

$$F_n=F_{n-1}+F_{n-2}$$