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
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{?}\)
Consider the sequence \(\{f_{n+1}/f_n:n\ge1\}\) of ratios of consecutive terms of the Fibonacci sequence. Figure 9.1 shows these ratios for \(n\leq 18\text{.}\)
Figure9.1.The ratios \(f_{n+1}/f_{n}\) for \(n\leq 18\)
The ratios seem to be converging to a number. Can we determine this number? Does this number have anything to do with an explicit formula for \(f_n\) (if one even exists)?
Example9.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).
Subsection9.1.2Recurrences for strings
In Chapter 3, we saw several times how we could find recurrences that gave us the number of binary or ternary strings of length \(n\) when we place a restriction on certain patterns appearing in the string. Let’s recall a couple of those types of questions in order to help generate more recurrences to work with.
Example9.3.
Let \(a_{n}\) count the number of binary strings of length \(n\) in which no two consecutive characters are \(1\)’s. Evidently, \(a_1=2\) since both binary strings of length \(1\) are “good.” Also, \(a_2=3\) since only one of the four binary strings of length \(2\) is “bad,”, namely \((1,1)\text{.}\) And \(a_3= 5\text{,}\) since of the \(8\) binary strings of length \(3\text{,}\) the following three strings are “bad”:
More generally, it is easy to see that the sequence satisfies the recurrence \(a_{n+2} = a_{n+1}+a_n\text{,}\) since we can partition the set of all “good” strings into two sets, those ending in \(0\) and those ending in \(1\text{.}\) If the last bit is \(0\text{,}\) then in the first \(n+1\) positions, we can have any “good” string of length \(n+1\text{.}\) However, if the last bit is \(1\text{,}\) then the preceding bit must be \(0\text{,}\) and then in the first \(n\) positions we can have any “good” string of length \(n\text{.}\)
As a result, this sequence is just the Fibonacci numbers, albeit offset by \(1\) position, i.e, \(a_{n} = f_{n+1}\text{.}\)
Example9.4.
Let \(t_n\) count the number of ternary strings in which we never have \((2,0)\) occurring as a substring in two consecutive positions. Now \(t_1=3\) and \(t_2=8\text{,}\) as of the \(9\) ternary strings of length \(2\text{,}\) exactly one of them is “bad.” Now consider the set of all good strings grouped according to the last character. If this character is a \(2\) or a \(1\text{,}\) then the preceding \(n+1\) characters can be any “good” string of length \(n+1\text{.}\) However, if the last character is a \(0\text{,}\) then the first \(n+1\) characters form a good string of length \(n+1\) which does not end in a \(2\text{.}\) The number of such strings is \(t_{n+1} - t_n\text{.}\) Accordingly, the recurrence is \(t_{n+2} = 3t_{n+1} - t_n\text{.}\) In particular, \(t_3 = 21\text{.}\)
Subsection9.1.3Lines and regions in the plane
Our next example takes us back to one of the motivating problems discussed in Chapter 1. In Figure 9.5, we show a family of \(4\) lines in the plane. Each pair of lines intersects and no point in the plane belongs to more than two lines. These lines determine \(11\) regions.
Figure9.5.Lines and Regions
We ask how many regions a family of \(1000\) lines would determine, given these same restrictions on how the lines intersect. More generally, let \(r_n\) denote the number of regions determined by \(n\) lines. Evidently, \(r_1=2\text{,}\)\(r_2=4\text{,}\)\(r_3=7\) and \(r_4=11\text{.}\) Now it is easy to see that we have the recurrence \(r_{n+1} = r_n+n+1\text{.}\) To see this, choose any one of the \(n+1\) lines and call it \(l\text{.}\) Line \(l\) intersects each of the other lines and since no point in the plane belongs to three or more lines, the points where \(l\) intersects the other lines are distinct. Label them consecutively as \(x_1,x_2,\dots,x_n\text{.}\) Then these points divide line \(l\) into \(n+1\) segments, two of which (first and last) are infinite. Each of these segments partitions one of the regions determined by the other \(n\) lines into two parts, meaning we have the \(r_n\) regions determined by the other \(n\) lines and \(n+1\) new regions that \(l\) creates.
