Recursive Counting

What you need to know

• Setting up a recursion. Let $a_n$ be the count for size $n$. Sort the objects by their last piece (the last tile, last letter, or last jump). Removing that piece leaves a smaller object, so $a_n$ is a sum of earlier terms.
• Fibonacci-type recursions. Tilings of a $1\times n$ board by $1\times1$ squares and $1\times2$ dominoes: the last piece is a square (leaving $n-1$ cells) or a domino (leaving $n-2$), so $a_n = a_{n-1}+a_{n-2}$, with $a_1 = 1$ and $a_2 = 2$. Strings of $0$s and $1$s with no two $1$s in a row follow the same rule, starting from $a_1 = 2$ and $a_2 = 3$. Example: tilings for $n = 1$ to $6$: $1, 2, 3, 5, 8, 13$. Strings: $2, 3, 5, 8, 13, 21$.
• Avoiding longer patterns. Avoiding three in a row (say, no three heads in a row) gives a longer recursion such as $a_n = a_{n-1}+a_{n-2}+a_{n-3}$. Or keep a separate count for each length of the run at the end (states).
• When every earlier term appears. A recursion like $a_n = a_{n-1}+a_{n-2}+\dots+a_1+c$, where $c$ is a fixed number, doubles at every step from $a_2$ on, so its terms are powers of $2$ times a fixed number. Why: subtracting the equation for $a_{n-1}$ from the one for $a_n$ leaves $a_n-a_{n-1} = a_{n-1}$. Example: the number $a_n$ of ways to write $n$ as an ordered sum of positive whole numbers satisfies $a_n = a_{n-1}+\dots+a_1+1$ (the last part is $1, 2, \dots, n-1$, or all of $n$). So the counts are $1, 2, 4, 8, \dots = 2^{n-1}$.

How AMC 10 tests it

• Problems 10–18: sequences of $8$ to $12$ coin flips that avoid a pattern, or domino tilings of a $2\times n$ board, meant for a recursion worked out by hand.
• Problems 14–22: climbing stairs $1$ or $2$ steps at a time, or a frog jumping $1$ or $2$ lily pads with some pads not allowed.
• Problems 18–24: a process defined step by step, where you must find a pattern or a formula.
• Recursions also power many probability problems (see conditional probability and states).

Standard approaches

1. Find what builds the object from a smaller one (usually the last piece or the first choice) and write $a_n$ from that.
2. Set the starting values carefully ($a_0 = 1$, counting the empty object once, is often right). Then fill in a table up to the $n$ you need.
3. If one recursion does not close up, keep two counts: for example, $b_n$ for strings ending in $1$ and $c_n$ for strings ending in $0$.
4. If you cannot see the recursion, list small cases, guess the rule from the numbers, then explain why it holds.
5. Check a tiling count with casework on the number of dominoes. With $k$ dominoes there are $n-k$ pieces, and $\binom{n-k}{k}$ ways to choose which pieces are dominoes; add these up. Example: for $n = 5$, $\binom50+\binom41+\binom32 = 1+4+3 = 8$, matching $a_5$.

Worked example

How many sequences of $10$ coin flips contain no three consecutive tails?

(A) $274$ (B) $448$ (C) $504$ (D) $644$ (E) $927$

Solution.

Step 1: name the count. Let $a_n$ be the number of sequences of $n$ flips with no TTT in them. Call these "good."

Step 2: sort by the ending. A good sequence of length $n\ge3$ cannot end in TTT, so it ends in exactly one of H, HT, or HTT (its last H and the tails after it). Taking off that ending leaves any good sequence of length $n-1$, $n-2$, or $n-3$. So $a_n = a_{n-1}+a_{n-2}+a_{n-3}$.

Step 3: starting values. $a_0 = 1$ (the empty sequence), $a_1 = 2$, and $a_2 = 4$ (sequences this short cannot contain TTT).

Step 4: fill in the table. Each entry is the sum of the three before it. For example, $a_3 = 4+2+1 = 7$ (all $8$ sequences except TTT).

Last, $a_{10} = 274+149+81 = 504$.

The answer is $\boxed{\textbf{(C)}\ 504}$.

Pitfalls

• Wrong starting values, especially $a_0$. One wrong value early on spoils the whole table.
• Sorting by the ending in a way that misses some objects or counts some twice. "Ends in T" and "ends in TT" overlap: every sequence ending in TT also ends in T.
• Arithmetic slips while filling in the table. Write every term, and add each one twice.
• Assuming every "$1$ or $2$" problem is plain Fibonacci without checking whether the pieces come in colors. With $1\times1$ squares in $2$ colors, the rule becomes $a_n = 2a_{n-1}+a_{n-2}$.

Traps that recur

• Miscounting the free digits in the complement: each must be at least j, so there are 5 - j values for it, not 5 - j + 1 or 5. (2022 AMC 10A #24)
• Writing the recurrence as Fibonacci (a_n = a_{n-1} + a_{n-2}) and getting a wrong count, or forgetting the block '110' and allowing '1110'. (2019 AMC 10B #25)
• Treating the eight seats as a row (55 arrangements) and ignoring that the first and last people are also neighbors. (2015 AMC 10A #22)