Recursive Counting

## What you need to know
- Recurrence setup: let $a_n$ be the count for size $n$; classify objects by their last piece (last tile, last letter, last jump) to express $a_n$ through smaller values.
- Fibonacci-type: tilings of a $1 \times n$ board by squares and dominoes satisfy $a_n = a_{n-1} + a_{n-2}$ with $a_1 = 1$, $a_2 = 2$; binary strings with no two consecutive $1$s satisfy the same recurrence with $a_1 = 2$, $a_2 = 3$.
- Avoiding a longer pattern (no three consecutive heads) gives a longer recurrence such as $a_n = a_{n-1} + a_{n-2} + a_{n-3}$, or a state system tracking the current run.
- Recurrences of the form $a_n = a_{n-1} + \cdots + a_1 + c$ usually produce powers of $2$.

## How AMC 10 tests it
- Problems 10–18: coin-flip sequences of length $8$ to $12$ avoiding a pattern, or domino tilings of a $2 \times n$ board, intended for a recurrence iterated by hand.
- Problems 14–22: staircase climbing by $1$ or $2$ steps, or a frog jumping $1$ or $2$ pads with some pads forbidden.
- Problems 18–24: a recursively defined process where a pattern or closed form must be found.
- Recurrences also drive many probability problems (see conditional probability and states).

## Standard approaches
1. Identify what determines an object from a smaller one, usually the last element or the first choice, and write $a_n$ accordingly.
2. Set base cases carefully ($a_0 = 1$ for the empty object is often correct), then tabulate up to the needed $n$.
3. If one recurrence does not close, add states: $b_n$ for strings ending in $1$, $c_n$ for strings ending in $0$.
4. If the recurrence is unclear, list small cases, guess it from the data, then justify it.
5. Cross-check with casework on the number of dominoes: $\sum_k \binom{n-k}{k}$.

## 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. Let $a_n$ be the number of valid sequences of length $n$. Every valid sequence of length $n \ge 3$ ends in $H$, $HT$, or $HTT$, preceded by a valid shorter sequence, so $a_n = a_{n-1} + a_{n-2} + a_{n-3}$, with $a_0 = 1$, $a_1 = 2$, $a_2 = 4$. Iterating: $a_3 = 7$, $a_4 = 13$, $a_5 = 24$, $a_6 = 44$, $a_7 = 81$, $a_8 = 149$, $a_9 = 274$, $a_{10} = 504$. Answer $\boxed{\textbf{(C)}\ 504}$.

## Pitfalls
- Wrong base cases, especially $a_0$; an off-by-one error propagates through the whole table.
- Classifying by the ending in a way that is not exhaustive or not disjoint ("ends in T" and "ends in TT" overlap).
- Arithmetic slips while iterating; write every term and re-add once.
- Assuming every "$1$ or $2$" problem is plain Fibonacci without checking whether pieces come in colors.

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)