Turning a Word Puzzle Into a Recurrence

A staircase has $n$ steps. You can climb it taking either 1 or 2 steps at a time. How many distinct ways are there to climb the whole staircase?

Try small cases by hand before reading on — the goal isn't the final formula, it's noticing the mechanical rule that turns the story into an equation.

The translation move

A recurrence relates the answer for a given size to the answer for smaller sizes. To find it, don't think about the whole staircase at once — condition on the very last move. Ask: "how did I arrive at step $n$?" There are exactly two ways to have just landed on step $n$: you took a single step from step $n-1$, or you took a double step from step $n-2$. Every valid climb ends in exactly one of these two ways, and the two cases don't overlap.

So the number of ways to reach step $n$, call it $W(n)$, is the number of ways to have reached step $n-1$ (then take one more single step) plus the number of ways to have reached step $n-2$ (then take one double step):

$W(n) = W(n-1) + W(n-2)$

That's a recurrence — the Fibonacci recurrence, in fact, though the staircase story gives no hint of that until you derive it.

Solving the staircase

Base cases first — the recurrence needs somewhere to bottom out. $W(1) = 1$ (only one way: a single step). $W(2) = 2$ (either two singles, or one double). Now grind forward:

$W(3) = W(2)+W(1) = 2+1 = 3$ $W(4) = W(3)+W(2) = 3+2 = 5$ $W(5) = W(4)+W(3) = 5+3 = 8$

So for a 5-step staircase, there are 8 distinct ways to climb it. Sanity check $W(3)=3$ by hand: 1-1-1, 1-2, 2-1 — exactly three, matching.

A second example: tiling a 2×n board

How many ways can you tile a $2 \times n$ board using $1\times2$ dominoes (each domino covers exactly two adjacent squares, placed either horizontally or vertically)?

Condition on how the rightmost column is covered. Two cases: either it's covered by a single vertical domino (leaving a $2\times(n-1)$ board to tile the rest of, contributing $T(n-1)$ ways), or the rightmost two columns are covered together by two horizontal dominoes stacked on top of each other (leaving a $2\times(n-2)$ board, contributing $T(n-2)$ ways) — no other way to cover the rightmost column is possible without leaving a gap. So:

$T(n) = T(n-1) + T(n-2)$

Same recurrence shape as the staircase — not a coincidence, since both are "count the ways, conditioning on the last unit of structure, where the last unit is either size 1 or size 2." Base cases: $T(1)=1$ (one vertical domino), $T(2)=2$ (two verticals, or two horizontals stacked). Then $T(3)=T(2)+T(1)=3$, $T(4)=T(3)+T(2)=5$, $T(5)=T(4)+T(3)=8$. A $2\times5$ board has 8 tilings — the identical numbers as the staircase, because it's the identical recurrence with identical base cases.

Generalizing past the last move

Not every recurrence conditions on the immediately preceding unit — sometimes you need to condition on where a particular element sits ("where is the largest number placed") or split into more than two cases (a staircase allowing 1, 2, or 3 steps gives $W(n) = W(n-1)+W(n-2)+W(n-3)$, the "tribonacci" recurrence). The reusable skill, though, is always the same first move: identify the very last decision that produces a size-$n$ object, enumerate the finitely many ways that decision could have gone, and express the count for each way in terms of a strictly smaller version of the same problem. That translation is 90% of solving any "count the ways" interview question — the arithmetic that follows is the easy part.