Math Core

Some counts have no neat closed formula, but each case is built from smaller cases in a predictable way. Instead of counting size $12$ directly, you find how size $n$ depends on sizes $n - 1$ , $n - 2$ , and so on, then fill in a short table. On the AIME the numbers stay small enough to compute by hand.

Condition on the last step

The standard move is to look at how an object ends. Split the objects of size $n$ by their last piece, and notice that removing that piece leaves a smaller object of the same kind.

For example, let $a_n$ be the number of ways to climb $n$ stairs taking $1$ or $2$ steps at a time. The last move is either a $1$ -step (after which $n - 1$ stairs were climbed in any valid way) or a $2$ -step (after $n - 2$ stairs). So

$a_n = a_{n-1} + a_{n-2}, \qquad a_0 = 1, \ a_1 = 1.$

That gives $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots$ , the Fibonacci numbers.

Building a recursion

Define $a_n$ precisely, including what $a_0$ means (usually $1$ : the empty object).
Split the objects of size $n$ into cases by their last piece (or first piece).
Show that each case is in bijection with objects of a smaller size.
Compute the first few terms by hand to check, then run the table up to $n$ .

When one sequence isn't enough

Sometimes the last piece alone doesn't tell you whether you can extend. Then track several sequences, one for each possible ending. For strings of $A$ , $B$ , $C$ with no $AB$ anywhere, what you may append depends on whether the string ends in $A$ . Let $x_n$ count valid strings ending in $A$ and $y_n$ those ending in $B$ or $C$ :

$x_{n+1} = x_n + y_n, \qquad y_{n+1} = x_n + 2y_n.$

(After an $A$ you may add $A$ or $C$ ; after $B$ or $C$ you may add anything.)

This "state" bookkeeping is the same idea you'll use for probability with states later in this unit.

Tilings

Tiling a strip with pieces of lengths $1$ and $2$ is the stair problem again. Wider boards need more care. For $3 \times n$ boards and dominoes, look at how the left edge can be covered. For even $n$ the count $t_n$ satisfies

$t_n = 4t_{n-2} - t_{n-4}, \qquad t_0 = 1, \ t_2 = 3,$

giving $1, 3, 11, 41, 153, 571, \dots$ (and $t_n = 0$ for odd $n$ , since $3n$ squares can't be split into dominoes).

Common mistake

Check the first two or three terms by listing objects directly. Most wrong recursions give the right shape with the wrong starting values, and one wrong initial value ruins every later term.

Worked example: Stairs

In how many ways can you climb $10$ stairs taking $1$ or $2$ steps at a time?

Continue the Fibonacci table from $a_0 = a_1 = 1$ : $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89$ . The answer is $a_{10} = 89$ .

Worked example: No three 1s in a row

How many binary strings of length $10$ contain no three consecutive $1$ s?

A valid string ends in $0$ , $01$ , or $011$ , and removing that ending leaves any valid shorter string. So $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ with $a_0 = 1$ , $a_1 = 2$ , $a_2 = 4$ :

$1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504.$

The answer is $a_{10} = 504$ .

Worked example: A 3 by 6 board

In how many ways can a $3 \times 6$ board be tiled by $1 \times 2$ dominoes?

Let $t_n$ count tilings of $3 \times n$ and $u_n$ count tilings of a $3 \times n$ board with one corner square removed. Covering the left column of a full board: either three horizontal dominoes stack there (leaving a $3 \times (n - 2)$ board), or a vertical domino covers two of the three squares and a horizontal one covers the third (two mirror-image ways, each leaving a board with a corner removed). So $t_n = t_{n-2} + 2u_{n-1}$ . Similarly $u_n = t_{n-1} + u_{n-2}$ .

Starting from $t_0 = 1$ , $u_1 = 1$ : $t_2 = 1 + 2 = 3$ , $u_3 = 3 + 1 = 4$ , $t_4 = 3 + 8 = 11$ , $u_5 = 11 + 4 = 15$ , $t_6 = 11 + 30 = 41$ .

Tip

For "remainder when divided by $1000$ " questions with big recursions, keep only the last three digits at every step. The recursion still works modulo $1000$ .

Practice

Practice 1

A child climbs a staircase of $12$ steps, taking $1$ , $2$ , or $3$ steps at a time. In how many ways can the child reach the top?