Math Core

Some counting and probability problems have no clean formula you can write down directly, but they have a clean relationship between a problem and smaller copies of itself. Recursion counts things by building them one step at a time. Its probability twin, the states method, tracks "where you are" in a random process and writes an equation for each state. Both are late-AMC staples.

Counting with recursion

Suppose you want the number of ways to climb a staircase of $n$ steps taking $1$ or $2$ steps at a time. Call it $a_n$ . Look at the first move:

If it's a $1$ -step, the rest is a climb of $n - 1$ steps: $a_{n-1}$ ways.
If it's a $2$ -step, the rest is a climb of $n - 2$ steps: $a_{n-2}$ ways.

So $a_n = a_{n-1} + a_{n-2}$ , with $a_1 = 1$ and $a_2 = 2$ . These are the Fibonacci numbers: $1, 2, 3, 5, 8, 13, 21, 34, \dots$

Building a recursion

Define $a_n$ = the number of valid objects of size $n$ .
Split by what happens first (or last): the first tile, the first letter, the first move.
Each case leaves a smaller valid object. Write $a_n$ in terms of earlier terms.
Compute a few starting values by hand, then iterate. On the AMC, iterating up to $n = 10$ or $12$ by hand is normal.

When a restriction depends on what came just before (like "no two consecutive $1$ s"), split by how the object starts until the restriction is resolved. A string with no two consecutive $1$ s either starts with $0$ (then anything valid of length $n - 1$ follows) or starts with $10$ (then anything valid of length $n - 2$ ). Again $a_n = a_{n-1} + a_{n-2}$ .

Probability with states

In a random process, a state is all the information about the present that matters for the future. Let $p_S$ be the probability of winning from state $S$ . Condition on the next step:

$p_S = \sum_{\text{next state } T} P(S \to T) \cdot p_T.$

This gives one linear equation per state. Solve the system. The same idea works for expected values, with an extra " $+1$ " for the step you just took.

Worked example: Tiling a strip

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

Let $t_n$ be the number of tilings of a $1 \times n$ strip. The leftmost tile is a square (leaving $t_{n-1}$ ) or a domino (leaving $t_{n-2}$ ), so $t_n = t_{n-1} + t_{n-2}$ with $t_1 = 1$ , $t_2 = 2$ :

$1, 2, 3, 5, 8, 13, 21, 34, 55, 89.$

So $t_{10} = 89$ .

Worked example: Stairs with three step sizes

How many ways can you climb $10$ stairs taking $1$ , $2$ or $3$ steps at a time?

Now $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ , with $a_0 = 1$ (one way to climb nothing), $a_1 = 1$ , $a_2 = 2$ :

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$a_n$	$1$	$1$	$2$	$4$	$7$	$13$	$24$	$44$	$81$	$149$	$274$

The answer is $274$ .

Worked example: A dice race

Alex and Blair take turns rolling a fair die, Alex first. The first person to roll a $6$ wins. What is the probability that Alex wins?

Let $p$ be the probability that the player about to roll eventually wins. Alex wins right away with probability $\tfrac16$ . Otherwise ( $\tfrac56$ ), Blair becomes the player about to roll, and Alex wins only if Blair doesn't: probability $1 - p$ . So

$p = \frac16 + \frac56(1 - p) \quad\Longrightarrow\quad \frac{11}{6}p = 1 \quad\Longrightarrow\quad p = \frac{6}{11}.$

Common mistake

Check your starting values carefully. Most recursion errors are off-by-one mistakes in $a_0$ , $a_1$ or $a_2$ . Always verify the recursion on a case small enough to list by hand, such as $n = 3$ or $n = 4$ .

Worked example: A frog on a triangle

A frog sits on vertex $A$ of a triangle $ABC$ . Each second it jumps to one of the other two vertices, each with probability $\tfrac12$ . What is the probability that it is back at $A$ after $4$ jumps?

Let $p_n$ be the probability it's at $A$ after $n$ jumps. To be at $A$ after $n + 1$ jumps, it must be not at $A$ after $n$ jumps, then jump to $A$ (probability $\tfrac12$ ). So

$p_{n+1} = \tfrac12(1 - p_n), \qquad p_0 = 1.$

Then $p_1 = 0$ , $p_2 = \tfrac12$ , $p_3 = \tfrac14$ , $p_4 = \tfrac38$ .

Practice

Practice 1

In how many ways can you climb a staircase of $8$ steps if each move goes up $1$ or $2$ steps?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 2

Ana and Ben take turns flipping a fair coin, Ana first. The first person to flip heads wins. What is the probability that Ana wins?

Practice 3

How many subsets of $\{1, 2, 3, \dots, 12\}$ , including the empty set, contain no two consecutive integers?

Practice 4

How many strings of length $10$ made of the letters A and B contain no three consecutive A's?

Enter a number. Fractions like 3/4 and sqrt(2) are OK.

Practice 5

A bug starts at vertex $A$ of triangle $ABC$ . Each minute it crawls to one of the other two vertices, each with probability $\tfrac12$ . What is the probability that the bug is at $A$ after $6$ minutes?

Practice 6

How many strings of length $8$ using the digits $0$ , $1$ and $2$ contain no two consecutive $0$ s?

Practice 7

In how many ways can a $3 \times 8$ rectangle be tiled with $1 \times 2$ dominoes?

Practice 8

A gambler starts with $3$ chips. Each round, she wins a chip with probability $\tfrac23$ or loses a chip with probability $\tfrac13$ . She stops when she has $5$ chips or $0$ chips. What is the probability that she ends with $5$ chips?

Real contest practice

2020 AMC 10A, Problem 13: a frog's random walk in a square, solved with states and symmetry.
2015 AMC 10A, Problem 22: people around a table, no two neighbors standing; a recursion on seating patterns.
2019 AMC 10B, Problem 25: binary sequences with restrictions on consecutive digits.