Counting & ProbabilityDifficulty 30-9076 tagged problems

Recursive Counting

Recursive Counting is the habit of defining counts in terms of smaller counts and solving the resulting recurrence. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$a_n = a_{n-1} + a_{n-2}, \quad a_0 = a_1 = 1 \ (\text{a recurrence with base cases})$$

Express the count for size $n$ in terms of counts for smaller sizes, then use base cases to compute up.

Why It Works

1
Look at one structural feature of a size-$n$ object that, once fixed, leaves a smaller version of the same problem.
2
Sort all size-$n$ objects by that feature into disjoint cases; each case reduces to a count of size $n-1$, $n-2$, etc.
3
Adding the cases (casework!) gives a recurrence like $a_n = a_{n-1} + a_{n-2}$.
4
Pin down enough base cases to start, then compute $a_n$ step by step (or solve for a closed form).

Worked Examples

Example 1

How many ways can a $1 \times 10$ strip be tiled with $1 \times 1$ squares and $1 \times 2$ dominoes?

1
Let $a_n$ count tilings of a $1 \times n$ strip. Look at the leftmost tile.
2
If it is a square, the rest is a $1 \times (n-1)$ strip ($a_{n-1}$ ways); if a domino, the rest is $1 \times (n-2)$ ($a_{n-2}$ ways). So $a_n = a_{n-1} + a_{n-2}$.
3
Base cases: $a_0 = 1$ (empty tiling) and $a_1 = 1$ (one square).
4
Build up: $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89$, so $a_{10} = 89$.

Answer:

$89$

Warm-up

How many binary strings of length $6$ contain no two consecutive $1$s?

1
Let $a_n$ be the count for length $n$. Condition on the last bit: if it is $0$, the first $n-1$ bits form any valid string ($a_{n-1}$); if it is $1$, the bit before must be $0$ and the first $n-2$ bits are any valid string ($a_{n-2}$).
2
So $a_n = a_{n-1} + a_{n-2}$, the Fibonacci recurrence.
3
Base cases: $a_1 = 2$ (the strings $0, 1$) and $a_2 = 3$ ($00, 01, 10$).
4
Build up: $a_3 = 5, a_4 = 8, a_5 = 13, a_6 = 21$.

Answer:

$21$

Contest level

A staircase has $10$ steps. You climb $1$ or $2$ steps at a time. How many distinct ways can you reach the top?

1
Let $f(n)$ be the number of ways to climb $n$ steps. Condition on the last move: a $1$-step from $n-1$, or a $2$-step from $n-2$.
2
So $f(n) = f(n-1) + f(n-2)$, with $f(1) = 1$ and $f(2) = 2$.
3
Build the sequence: $1, 2, 3, 5, 8, 13, 21, 34, 55, 89$.
4
Thus $f(10) = 89$.

Answer:

$89$

Olympiad / Challenge

How many ways can a $2 \times n$ rectangle be tiled by $1 \times 2$ dominoes, and what is the count for $n = 8$?

1
Let $T_n$ be the number of tilings of a $2 \times n$ board. Look at the left edge: either a single vertical domino covers it (leaving $2 \times (n-1)$), or two horizontal dominoes stack to cover the first two columns (leaving $2 \times (n-2)$).
2
These cases are disjoint and exhaustive, so $T_n = T_{n-1} + T_{n-2}$ — Fibonacci again.
3
Base cases: $T_1 = 1$ (one vertical domino) and $T_2 = 2$ (two verticals or two horizontals).
4
Build up: $T_3 = 3, T_4 = 5, T_5 = 8, T_6 = 13, T_7 = 21, T_8 = 34$.

Answer:

$34$

Going Deeper

The method generalizes: find a structural feature of a size-$n$ object whose removal leaves an independent smaller instance, and the casework over that feature yields a recurrence. The recurrence need not be order-$2$ — coin-change, ternary strings with forbidden patterns, and Catalan-type splits give recurrences of higher order or with convolution sums like $C_n = \sum_{i} C_i C_{n-1-i}$.
Recursion is the backbone of AIME counting: tilings, restricted strings, staircase/path problems, and any 'find a pattern' setup. Linear recurrences with constant coefficients also admit closed forms via characteristic roots (Fibonacci's Binet formula), and recursions often pair with generating functions for the closed form.
Pitfall: get the base cases and their indexing exactly right — an off-by-one in $a_0$ or $a_1$ propagates through every later term. Equally important, verify the cases in the recurrence are disjoint and exhaustive (no tiling counted under both 'starts vertical' and 'starts with two horizontals'), and confirm the smaller instance left behind is genuinely the same problem, not a constrained variant.

Spot the Signal

Look for problems where the key step is defining counts in terms of smaller counts and solving the resulting recurrence.
You can describe the hard part as defining counts in terms of smaller counts and solving the resulting recurrence, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the counting object that calls for recursive counting, then rewrite the givens around it.
Name the relation that makes Recursive Counting legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Recursive Counting just because the surface looks familiar; verify the required condition first.
Applying Recursive Counting because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let recursive counting reveal the counting structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is defining counts in terms of smaller counts and solving the resulting recurrence.