One of the most well-known recurrences arises from a simple story. Suppose that a scientist introduces a pair of newborn rabbits to an isolated island. This species of rabbits is unable to reproduce until their third month of life, but after that produces a new pair of rabbits each month. Thus, in the first and second months, there is one pair of rabbits on the island, but in the third month, there are two pairs of rabbits, as the first pair has a pair of offspring. In the fourth month, the original pair of rabbits is still there, as is their first pair of offspring, which are not yet mature enough to reproduce. However, the original pair gives birth to another pair of rabbits, meaning that the island now has three pairs of rabbits. Assuming that there are no rabbit-killing predators on the island and the rabbits have an indefinite lifespan, how many pairs of rabbits are on the island in the tenth month?
Let’s see how we can get a recurrence from this story. Let \(f_n\) denote the number of pairs rabbits on the island in month \(n\text{.}\) Thus, \(f_1 = 1\text{,}\) \(f_2 = 1\text{,}\) \(f_3=2\text{,}\) and \(f_4=3\) from our account above. How can we compute \(f_n\text{?}\) Well, in the \(n^\text{th}\) month we have all the pairs of rabbits that were there during the previous month, which is \(f_{n-1}\text{;}\) however, some of those pairs of rabbits also reproduce during this month. Only the ones who were born prior to the previous month are able to reproduce during month \(n\text{,}\) so there are \(f_{n-2}\) pairs of rabbits who are able to reproduce, and each produces a new pair of rabbits. Thus, we have that the number of rabbits in month \(n\) is \(f_n = f_{n-1} + f_{n-2}\) for \(n\geq 3\) with \(f_1=f_2=1\text{.}\) The sequence of numbers \(\{f_n\colon n\geq 0\}\) (we take \(f_0=0\text{,}\) which satisfies our recurrence) is known as the Fibonacci sequence after Leonardo of Pisa, better known as Fibonacci, an Italian mathematician who lived from about 1170 until about 1250. The terms \(f_0,f_1,\dots,f_{20}\) of the Fibonacci sequence are
\begin{equation*}
0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987, 1597,2584,4181,6765.
\end{equation*}
Thus, the answer to our question about the number of pairs of rabbits on the island in the tenth month is \(55\text{.}\) That’s really easy to compute, but what if we asked for the value of \(f_{1000}\) in the Fibonacci sequence? Could you even tell whether the following inequality is true or false—without actually finding \(f_{1000}\text{?}\)
\begin{equation*}
f_{1000} \lt 232748383849990383201823093383773932
\end{equation*}
Example 9.2.
The Fibonacci sequence would not be as well-studied as it is if it were only good for counting pairs of rabbits on a hypothetical island. Here’s another instance which again results in the Fibonacci sequence. Let
\(c_n\) count the number of ways a
\(2\times n\) checkerboard can be covered by
\(2\times 1\) tiles. Then
\(c_1=1\) and
\(c_2=2\) while the recurrence is just
\(c_{n+2} = c_{n+1}+c_n\text{,}\) since either the rightmost column of the checkerboard contains a vertical tile (and thus the rest of it can be tiled in
\(c_{n+1}\) ways) or the rightmost two columns contain two horizontal tiles (and thus the rest of it can be tiled in
\(c_n\) ways).
