maths.free › Combinatorics & Graph Theory › 9. Recurrence Equations › Introduction
Introduction
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.
Fibonacci numbers
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\). Thus, \(f_1 = 1\), \(f_2 = 1\), \(f_3=2\), and \(f_4=3\) from our account above. How can we compute \(f_n\)? 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}\); 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\), 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\). The sequence of numbers \(\{f_n\colon n\geq 0\}\) (we take \(f_0=0\), 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{aligned}\end{aligned}\]
Thus, the answer to our question about the number of pairs of rabbits on the island in the tenth month is \(55\). 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 falsewithout actually finding \(f_{1000}\)? \[\begin{aligned}\end{aligned}\]
Consider the sequence \(\{f_{n+1}/f_n:n\ge1\}\) of ratios of consecutive terms of the Fibonacci sequence. shows these ratios 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)?
Condensed — the full section is in Keller & Trotter, Applied Combinatorics.
Recurrences for strings
In , 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.
Example
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)\). And \(a_3= 5\), since of the \(8\) binary strings of length\(3\), the following three strings are bad: \[\begin{aligned}\end{aligned}\] More generally, it is easy to see that the sequence satisfies the recurrence \(a_{n+2} = a_{n+1}+a_n\), since we can partition the set of all good strings into two sets, those ending in \(0\) and those ending in\(1\). If the last bit is\(0\), then in the first \(n+1\) positions, we can have any good string of length\(n+1\). However, if the last bit is\(1\), then the preceding bit must be \(0\), and then in the first \(n\) positions we can have any good string of length\(n\).
As a result, this sequence is just the Fibonacci numbers, albeit offset by\(1\) position, i.e, \(a_{n} = f_{n+1}\).
Example
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\), as of the \(9\) ternary strings of length\(2\), 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\), then the preceding \(n+1\) characters can be any good string of length\(n+1\). However, if the last character is a \(0\), then the first \(n+1\) characters form a good string of length \(n+1\) which does not end in a\(2\). The number of such strings is \(t_{n+1} - t_n\). Accordingly, the recurrence is \(t_{n+2} = 3t_{n+1} - t_n\). In particular, \(t_3 = 21\).
Lines and regions in the plane
Our next example takes us back to one of the motivating problems discussed in . In , 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.
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\), \(r_2=4\), \(r_3=7\) and \(r_4=11\). Now it is easy to see that we have the recurrence \(r_{n+1} = r_n+n+1\). To see this, choose any one of the \(n+1\) lines and call it \(l\). 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\). 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.
Symbols used here
i² = −1.
Inequalities that allow equality; < and > exclude it.
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
Number of k-element subsets of n things: n!/(k!(n−k)!).
Add a_k for k = 1 up to n.
Multiply a_k for k = 1 up to n.
The set with no elements; the number of elements of A.
Questions people ask
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges) — not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
Покушај сам.
Parts of this page are adapted from Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.
Више у Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion–exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs