Discrete Mathematics and Proof

Setting up a recurrence from a counting problem

A count for size 20 is hard to list, but the objects of size 20 are built from smaller ones. How do you turn that into a rule that computes every count from the ones before it?

You need

The Fibonacci sequenceDiscrete Mathematics and Proof

Where you are 6 in Recurrence relations

Logic, proof and discrete math6

Recurrence relations6

Closed form versus recursive form Generating a sequence from a rule The Fibonacci sequence

Setting up a recurrence from a counting problem

Solving and checking a two-term recurrence Two-term recurrences with a repeated root

When you reach for it

Some counts have no quick formula but have an obvious way to grow: a tiling of a long strip is a tiling of a shorter strip plus one tile, and a string is a shorter string plus one letter. When the objects of size n are built from objects of the same kind and smaller size, the count a_n can be written in terms of a_{n-1}, a_{n-2} and so on. That equation, with enough starting values, is a recurrence, and it computes every term exactly (Generating a sequence from a rule).

Reach for it when listing works for small n but the objects are too many to list later, and when the structure of one object can be read off from its first or last piece. The recurrence is also the input to Solving and checking a two-term recurrence, which turns many such rules into closed formulas.

The procedure

Day 1: sort by the last piece

Everything rests on the addition principle (Counting): if a finite set is split into pieces with no element in two pieces and every element in some piece, its size is the sum of the sizes of the pieces.

Name the count. Say exactly what a_n counts, including what size 0 would mean. Often there is one object of size 0, the empty one, and taking a_0 = 1 makes the rule work from small n.

Sort by what happens at one end. Look at the last piece (or the first): the last tile, the last letter, the last stride. Each possible last piece gives a case. The cases must be disjoint (an object has only one last piece) and must cover everything (every object of size n \ge 1 has a last piece). Then the addition principle applies.

Count each case by a smaller count. Removing the last piece should give an object of the same kind and smaller size, and every such smaller object should arise exactly once. That is a bijection (One-to-one, onto and bijective functions) between the case and the smaller set, so the case has a_{n-1} or a_{n-2} members. When removing the piece leaves an object with an extra condition, look one more piece back until the condition is gone (Example 2).

Read off the rule and its range. Add the cases, and say for which n every case makes sense.

Find enough starting values. A rule that reaches back k places needs k starting values, counted directly. Then compute a few more terms from the rule and check them against a list made by hand: a brute-force listing for small n catches a missed or double-counted case.

Day 2: when the cases depend on n

Two things can make the rule less tidy. The number of cases can grow with n: if item 1 can go to any of n - 1 places, a coefficient n - 1 appears (Example 4), and if a new line crosses n - 1 old ones, the added amount depends on n (Example 7). Or the first piece can have any size: if a string splits as a first block of size k and a rest of size n - 1 - k, the product principle counts each split and the rule is a sum over k (Example 6). The method is the same: sort, check disjoint and complete, count each case by smaller counts.

Worked examples

Example 1

Day 1: squares and dominoes, and a row of coins

Valter covers a 1 by n strip with 1 by 1 squares and 1 by 2 dominoes. Let t_n be the number of tilings. Find a recurrence for t_n. Then count the ways to pay \$10 into a machine with \$1 and \$2 coins, one coin at a time, where the order of the coins matters.

Solution

Sort the tilings of length n \ge 2 by the last tile. If it is a square, removing it leaves a tiling of length n - 1; conversely, any tiling of length n - 1 with a square added is a tiling ending in a square. So there are t_{n-1} of these. If it is a domino, the same argument gives t_{n-2}. No tiling ends in both, and every tiling ends in one, so

t_n = t_{n-1} + t_{n-2} \quad (n \ge 2).

The rule reaches back two places, so two starting values: t_0 = 1 (the empty strip has one tiling, with no tiles) and t_1 = 1. Then t_2 = 2, t_3 = 3, t_4 = 5, which the figure confirms by listing.

Figure 1The t_4 = 5 tilings of a 1 by 4 strip, sorted by the last tile. Taking that tile off leaves every tiling of length 3 once, or every tiling of length 2 once.

Since t_0 = 1 = F_1 and t_1 = 1 = F_2, and both sequences obey “add the last two”, strong induction gives t_n = F_{n+1} for every n \ge 0 (The Fibonacci sequence).

A payment of n dollars is a sequence of 1s and 2s adding to n. Reading each \$1 coin as a square and each \$2 coin as a domino matches payments with tilings one to one, so the payments of \$10 number t_{10} = F_{11} = 89. Sorting the payments by their last coin gives the same rule directly, which is the bijection seen from the other side.

Example 2

Day 1: no two a’s side by side

Let g_n be the number of strings of length n over the alphabet \{a, b, c\} with no two a’s in a row. Find a recurrence and compute g_6.

Solution

Sort the good strings of length n \ge 2 by the last letter.

Last letter b or c. Removing it leaves any good string of length n - 1, and adding b or c to a good string never creates aa. That is 2g_{n-1} strings.

Last letter a. Now the shorter string is not arbitrary: it must not end in a. So look one more letter back. The letter before the final a is b or c, and before that sits any good string of length n - 2. That is 2g_{n-2} strings.

The cases are disjoint and cover every good string, so

g_n = 2g_{n-1} + 2g_{n-2} \quad (n \ge 2).

Starting values: g_0 = 1 and g_1 = 3. Then g_2 = 8, g_3 = 22, g_4 = 60, g_5 = 164 and g_6 = 2 \cdot 164 + 2 \cdot 60 = 448.

Check by listing. Of the 27 strings of length 3, those containing aa are aaa, aab, aac, baa, caa, so 27 - 5 = 22 are good. With only two letters \{0, 1\} and “no two 1s in a row”, the same sorting gives s_n = s_{n-1} + s_{n-2} with s_0 = 1, s_1 = 2, so s_n = F_{n+2}; those strings mark the subsets with no two consecutive integers that Combinatorial proof: counting one set two ways counts by a bijection.

Example 3

Day 1: strides of one, two or three

Valter climbs a staircase of 12 steps, each stride covering 1, 2 or 3 steps. In how many orders of strides can he reach the top?

Solution

Let s_n count the climbs of n steps. Sort them by the last stride. A last stride of 1, 2 or 3 leaves a climb of n - 1, n - 2 or n - 3 steps, and every such climb extends in exactly one way. So

s_n = s_{n-1} + s_{n-2} + s_{n-3} \quad (n \ge 3),

which needs three starting values: s_0 = 1 (standing still), s_1 = 1, s_2 = 2. Check by listing: s_3 = 4 (1{+}1{+}1, 1{+}2, 2{+}1, 3) and s_4 = 7 (1111, 112, 121, 211, 22, 13, 31), both as the rule says. Continuing,

n	s_n	n	s_n
5	13	9	149
6	24	10	274
7	44	11	504
8	81	12	927

so there are 927 climbs. Sorting by the first stride gives the same rule; either end works, because removing a stride from either end leaves a shorter climb of the same kind.

Example 4

Day 2: derangements by the first item

A derangement of \{1, \dots, n\} is a permutation \sigma with \sigma(i) \ne i for every i, and D_n is their number (Inclusion-exclusion for three or more sets, and derangements counts them by a formula). Prove that D_n = (n - 1)(D_{n-1} + D_{n-2}) for n \ge 3, and check it against a listing for n = 4.

Solution

Proof. Sort the derangements by k = \sigma(1); there are n - 1 choices, k \in \{2, \dots, n\}. Fix k and split once more.

Case A: \sigma(k) = 1. Items 1 and k trade places, and \sigma restricted to the other n - 2 items is a derangement of them. Every derangement of those n - 2 items arises once: D_{n-2}.

Case B: \sigma(k) \ne 1. Some j \ne k has \sigma(j) = 1. Define \tau on \{2, \dots, n\} by \tau(j) = k and \tau(i) = \sigma(i) otherwise. Since \sigma sends \{2, \dots, n\} one to one onto \{1, \dots, n\} without k, and \tau only replaces the value 1 by k, \tau is a permutation of \{2, \dots, n\}. It fixes nothing: \tau(j) = k \ne j, and \tau(i) = \sigma(i) \ne i for i \ne j. Conversely, from a derangement \tau of \{2, \dots, n\}, let j = \tau^{-1}(k), set \sigma(1) = k, \sigma(j) = 1 and \sigma = \tau elsewhere; this is a derangement with \sigma(k) = \tau(k) \ne 1. The two maps undo each other, so Case B has D_{n-1} members.

So each k gives D_{n-1} + D_{n-2}, and the n - 1 values of k give the rule. \square

With D_1 = 0 and D_2 = 1: D_3 = 2(1 + 0) = 2, D_4 = 3(2 + 1) = 9, D_5 = 4(9 + 2) = 44, D_6 = 5(44 + 9) = 265, matching the inclusion-exclusion table. The nine derangements of \{1, 2, 3, 4\}, written as \sigma(1)\sigma(2)\sigma(3)\sigma(4), sorted by \sigma(1):

\sigma(1) = 2	\sigma(1) = 3	\sigma(1) = 4
2143	3412	4321
2341	3142	4123
2413	3421	4312

The first row is Case A in each column (D_2 = 1), the other two are Case B (D_3 = 2).

Example 5

Day 2: a 2 by n board with dominoes and squares

Let w_n count the tilings of a 2 by n board by dominoes (either way round) and 2 by 2 squares. Find a recurrence, then guess and prove a closed formula.

Solution

Look at the top cell of the last column. A vertical domino covers it and the whole last column, leaving a 2 by (n - 1) board: w_{n-1} tilings. A horizontal domino covers it and the top cell of column n - 1; then the bottom-right cell can only take a second horizontal domino, leaving a 2 by (n - 2) board: w_{n-2}. A square covers the last two columns: w_{n-2}. So

w_n = w_{n-1} + 2w_{n-2} \quad (n \ge 2),

with w_0 = w_1 = 1.

Figure 2The w_3 = 5 tilings of a 2 by 3 board, sorted by what covers the right end. The counts 3 + 1 + 1 are w_2 + w_1 + w_1.

The terms are 1, 1, 3, 5, 11, 21, 43, 85. Each is about double the one before, alternately one more and one less, which suggests \displaystyle w_n = \frac{2^{n+1} + (-1)^n}{3}. Proof. Strong induction. For n = 0 and n = 1 the formula gives \displaystyle \frac{3}{3} = 1 and \displaystyle \frac{3}{3} = 1. For n \ge 2, assuming it for n - 1 and n - 2,

\begin{aligned} w_n &= \frac{2^{n} + (-1)^{n-1}}{3} + \frac{2^{n} + 2(-1)^{n-2}}{3} \\ &= \frac{2^{n+1} - (-1)^{n} + 2(-1)^{n}}{3} = \frac{2^{n+1} + (-1)^n}{3}. \end{aligned}

\square Guessing needs luck; Solving and checking a two-term recurrence finds such formulas without guessing.

Example 6

Day 2: balanced parentheses

A string of n left and n right parentheses is balanced if every opening stretch of it has at least as many left as right parentheses. Let C_n count them, with C_0 = 1 (the empty string). Find a recurrence, check it at n = 3, and compute C_5.

Solution

In a balanced string with n \ge 1 pairs, the first symbol is “(“. Its partner is the first place where the opening stretch has equal numbers of each; it exists because the whole string balances. So the string is (A)B, where A is balanced (no opening stretch of it dips below zero, or the partner would come sooner) and B is balanced. If A has k pairs, B has n - 1 - k, with 0 \le k \le n - 1. Different k give different partners, so the cases are disjoint; any balanced A and B give a balanced (A)B, so by the product principle

C_n = \sum_{k=0}^{n-1} C_k \, C_{n-1-k} \quad (n \ge 1).

For n = 3 the rule says C_0C_2 + C_1C_1 + C_2C_0 = 2 + 1 + 2 = 5. The listing: k = 0: ()(()), ()()(); k = 1: (())(); k = 2: ((())), (()()). Five, as predicted. Then C_4 = 5 + 2 + 2 + 5 = 14 and

C_5 = 14 + 5 + 4 + 5 + 14 = 42.

These are the Catalan numbers. This lesson uses only their recurrence.

Example 7

Day 2: bent lines in the plane

A bent line is two rays from one corner point, not forming a straight line. Draw n bent lines so that every two cross in exactly 4 points, no three pass through one point, and no corner lies on another bent line. Find the number Z_n of regions.

The 4 crossings are an assumption about how the lines are drawn, not a fact about bent lines: each ray of one meets each ray of the other at most once, so two bent lines cross in at most 2 \cdot 2 = 4 points, but a careless drawing can give 3, 2 or none. The count below is for drawings where every pair reaches all 4.

Solution

One bent line cuts the plane into Z_1 = 2 regions, and Z_0 = 1. Add the n-th bent line to n - 1 others. It meets them in 4(n - 1) points, all different, which cut it into 4(n - 1) + 1 pieces (a bent line is one unbroken path, so m points cut it into m + 1 pieces). Each piece runs across one old region and splits it in two, and no other region changes. So

Z_n = Z_{n-1} + 4n - 3 \quad (n \ge 1).

Figure 3Two bent lines meeting in 4 points cut the plane into 7 regions. The second line is cut into 5 pieces, and each piece adds one region to the first line’s 2.

This rule adds an amount that depends on n. Unwinding it (Closed form versus recursive form),

\begin{aligned} Z_n &= 1 + \sum_{k=1}^{n} (4k - 3) \\ &= 1 + 2n(n + 1) - 3n = 2n^2 - n + 1. \end{aligned}

Check: Z_1 = 2, Z_2 = 7 as in the figure, Z_3 = 16, and Z_{10} = 191.

Boundaries

Disjoint and complete, or the sum is wrong. Sorting by the last piece works because every object has exactly one last piece. A sorting with overlapping cases double counts, and one that misses objects undercounts; the listing for small n is the test.
Removing a piece must leave the same kind of object. In Example 2, removing a final a leaves a string that must not end in a, which is not the set g_{n-1} counts; looking one more letter back fixed it. In Example 4, Case B needed a relabeling before it was a derangement.
A rule holds from some n on, and needs as many starting values as it reaches back. The cases of Example 2 need n \ge 2, and g_1 = 3 is not 2g_0 + 2g_{-1} for any sensible g_{-1}. Use a_0 = 1 only when “one empty object” fits the problem, and check a_2 directly when unsure.
Geometric counts need general position. Example 7 assumes four crossings per pair and no three through a point; fewer crossings give fewer regions.
A recurrence is not a closed formula. It gives each term from earlier ones. Closed formulas come from unwinding (Closed form versus recursive form), from a guess proved by induction, or from Solving and checking a two-term recurrence.

Where this goes next

Solving and checking a two-term recurrence solves rules such as w_n = w_{n-1} + 2w_{n-2} by trying powers, and Two-term recurrences with a repeated root handles the case where that try gives a double root. The same sorting, “is n in the subset or not”, gives Pascal’s rule \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} in pascals-triangle-recurrence.

Exercises

Day 1: setting up and computing

Valter tiles a 1 by n strip with squares and 1 by 3 bars. Find a recurrence for the number of tilings, with starting values, and compute the number for n = 12.
Count the ordered ways to pay \$10 with \$1, \$2 and \$5 coins, one coin at a time.
Find a recurrence for the number of strings of length n over \{a, b, c\} in which no two neighboring letters are equal, and find the number for n = 8.
Let e_n count the strings of length n over \{a, b, c, d\} with an even number of c’s. Show that e_n = 2e_{n-1} + 4^{n-1} for n \ge 1, check e_2 by listing, and find e_4.
Let h_n count the strings of length n over \{a, b, c\} in which every a is immediately followed by b. Find a recurrence and compute h_6.
Let q_n count the strings of length n over \{a, b\} with no three equal letters in a row. Show that q_n = q_{n-1} + q_{n-2} for n \ge 3, and check q_4 by listing every such string.

Day 1: reasoning

Fix one letter of a k-letter alphabet, k \ge 2. Prove that the number a_n of strings of length n with no two copies of that letter in a row satisfies a_n = (k - 1)(a_{n-1} + a_{n-2}) for n \ge 2.
Using the rule of Example 3, prove that the number s_n of climbs with strides 1, 2, 3 is odd exactly when n leaves remainder 0 or 1 on division by 4.
Explain why Example 2’s rule, used for n = 2, needs g_0 = 1, and why that value is the right one.

Day 2: setting up and computing

Use the recurrence and D_6 = 265 to find D_7 and D_8.
Squares now come in two colors, red and blue, alongside dominoes on a 2 by n board. Find a recurrence for the number v_n of tilings and compute v_6.
Twelve people sit around a round table and shake hands in six pairs at once, with no two arms crossing. Show that the number of ways for 2n people satisfies the Catalan recurrence with the same start, and find the number for twelve people.
Let I_n count the ways to split \{1, \dots, n\} into blocks of size 1 or 2. Prove that I_n = I_{n-1} + (n - 1)I_{n-2} for n \ge 2, check I_4 by listing, and find I_7.
A zigzag is two parallel rays joined by a segment from one starting point to the other. Assume the n zigzags are drawn so that every two cross in 9 points (the most possible, one for each of the 3 \cdot 3 pairs of pieces), no three pass through one point and no corner lies on another zigzag. Find a recurrence for the number of regions and the number for 4 zigzags.

Day 2: reasoning

Prove from the recurrence that D_n = nD_{n-1} + (-1)^n for every n \ge 2.
Find the flaw: “Item 1 goes to one of n - 1 places, and the other n - 1 items must then be deranged, so D_n = (n - 1)D_{n-1}.” Test the claim at n = 5.
A composition of n is a sequence of positive integers with sum n. Sort by the first part to show c_n = c_{n-1} + c_{n-2} + \cdots + c_0 for n \ge 1 with c_0 = 1, then prove that c_n = 2^{n-1} for n \ge 1.
Prove from its recurrence that every w_n in Example 5 is odd.
Explain why the Catalan recurrence needs C_0 = 1, and what it would give with C_0 = 0.

Answers

b_n = b_{n-1} + b_{n-3} for n \ge 3, by the last tile, with b_0 = b_1 = b_2 = 1. The terms from b_3 are 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, so b_{12} = 60.
128. By the last coin, p_n = p_{n-1} + p_{n-2} + p_{n-5}, with p_m = 0 for m < 0 and p_0 = 1. The terms p_1 to p_{10} are 1, 2, 3, 5, 9, 15, 26, 44, 75, 128.
x_n = 2x_{n-1} for n \ge 2, x_1 = 3: removing the last letter leaves any good string, and the last letter is either of the two letters unequal to its neighbor. So x_n = 3 \cdot 2^{n-1} and x_8 = 384.
e_4 = 136. By the last letter: a, b or d after a string with an even number of c’s, 3e_{n-1}; c after one with an odd number, 4^{n-1} - e_{n-1}. The total is 2e_{n-1} + 4^{n-1}. With e_0 = 1: e_1 = 3, e_2 = 10 (the 9 strings with no c, and cc), e_3 = 36, e_4 = 136.
h_n = 2h_{n-1} + h_{n-2} for n \ge 2, h_0 = 1, h_1 = 2. The string cannot end in a; a final c or a final b not after a gives 2h_{n-1}, and a final block ab gives h_{n-2}. Terms 5, 12, 29, 70, 169, so h_6 = 169.
Sort by the length of the final run of equal letters, 1 or 2. Removing it leaves a good string of length n - 1 or n - 2, and the removed letters must differ from that string’s last letter, so each shorter string extends once. With q_1 = 2, q_2 = 4: q_3 = 6, q_4 = 10. The list: aaba, aabb, abaa, abab, abba, baab, baba, babb, bbaa, bbab.
Proof. Call the letter x. A good string of length n \ge 2 ending in another letter is a good string of length n - 1 plus one of k - 1 letters: (k - 1)a_{n-1}. One ending in x has a non-x letter before it (k - 1 choices) and a good string of length n - 2 before that: (k - 1)a_{n-2}. The cases are disjoint and cover all. \square
Proof. Work modulo 2. The parities of s_0, s_1, s_2, s_3 are 1, 1, 0, 0. If the parities of s_{n-1}, s_{n-2}, s_{n-3} follow the pattern 1, 1, 0, 0 repeating, so does s_n: the sum of the three previous entries of the pattern is odd exactly when the entry being formed is 1 (check the four positions: 0 + 0 + 1, 1 + 0 + 0, 1 + 1 + 0, 0 + 1 + 1). Strong induction finishes. \square
At n = 2 the “ends in a” case is the strings ba and ca: a letter b or c before the final a, and before that a good string of length 0. There is exactly one, the empty string, so g_0 = 1, and the rule gives 2 \cdot 3 + 2 \cdot 1 = 8 = 9 - 1, which is right.
D_7 = 6(265 + 44) = 1854 and D_8 = 7(1854 + 265) = 14{,}833.
v_n = v_{n-1} + 3v_{n-2}, v_0 = v_1 = 1: the right end is a vertical domino, two horizontal dominoes, a red square or a blue square. Terms 4, 7, 19, 40, 97, so v_6 = 97.
132. Sort by the partner of person 1. The chord from person 1 must leave an even number of people on each side, 2k and 2(n - 1 - k), who shake hands only among themselves, since a handshake across the chord would cross it. So m_n = \sum_{k=0}^{n-1} m_k m_{n-1-k} with m_0 = 1, the Catalan rule, so m_n = C_n and twelve people give C_6 = 42 + 14 + 10 + 10 + 14 + 42 = 132.
Proof. Either n is alone in a block, leaving I_{n-1} splits, or it is paired with one of n - 1 others, leaving I_{n-2} splits of the rest. \square With I_0 = I_1 = 1: I_2 = 2, I_3 = 4, I_4 = 10, I_5 = 26, I_6 = 76, I_7 = 232. For n = 4: all singles (1), one pair (\binom{4}{2} = 6), two pairs (3), total 10.
R_n = R_{n-1} + 9(n - 1) + 1 with R_0 = 1: the new zigzag meets the old ones in 9(n - 1) points, is cut into 9(n - 1) + 1 pieces, and each splits a region. R_1 = 2, R_2 = 12, R_3 = 31, R_4 = 59.
Proof. Induction. n = 2: 2D_1 + 1 = 1 = D_2. If D_{n-1} = (n - 1)D_{n-2} + (-1)^{n-1}, the recurrence gives D_n = (n - 1)D_{n-1} + (n - 1)D_{n-2}. Replace (n - 1)D_{n-2} by D_{n-1} - (-1)^{n-1} to get D_n = nD_{n-1} + (-1)^n. \square
After \sigma(1) = k, item k may still go to place 1, so the rest is not a derangement of n - 1 items with their own places; the swap case (Case A) is left out. At n = 5 the claim gives 4D_4 = 36, but D_5 = 44. The gap 8 is 4D_3, the (n - 1)D_{n-2} swaps it missed.
The first part k (1 \le k \le n) is followed by any composition of n - k, so c_n = c_{n-1} + \cdots + c_0. Proof. c_1 = c_0 = 1 = 2^0. For n \ge 2, subtracting the rule for n - 1 from the rule for n gives c_n - c_{n-1} = c_{n-1}, so c_n = 2c_{n-1}, and induction gives c_n = 2^{n-1}. \square
Proof. w_0 = w_1 = 1 are odd. If w_{n-1} is odd, then w_n = w_{n-1} + 2w_{n-2} is odd plus even, so odd. \square
The terms k = 0 and k = n - 1 are the strings ()B and (A), where one part is empty, and there is exactly one empty string. With C_0 = 0 every term of the sum for C_1 would vanish, so every C_n would be 0.