The Fibonacci numbers F1, F2, F3… are well known.
They satisfy the following recurrence relation:
F*n = Fn*‒1 + F*n*‒2 for n ≥ 3, with F1 = 1 and F2 = 1.
The first values (below 200) are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 and 144. The value F0 = 0 is also sometimes included; this does not change the recurrence relation.
In his best-known work, the Liber Abaci, Leonardo Fibonacci describes the growth of a rabbit population as follows:
"Starting with one pair of rabbits, how many pairs will there be after a given number of months, if each pair produces a new pair every month and the new pair does not become fertile until its third month?"
Let F*n be the number of pairs at the beginning of the n*th month (assuming that the rabbits never die!). During each of the first two months, there is only one pair, so F1 = 1 and F2 = 1. In month n, the F*n rabbit pairs consist of the pairs from the previous month, numbering Fn*‒1, and the newly born pairs. However, in month n, only the pairs that already existed two months earlier can produce a new pair, so there are F*n*‒2 such pairs. This gives the recurrence relation above.
