How Many Ways Can You Climb n Stairs Using 2 or 3 at a Time?

Suppose you climb a staircase of $n$ stairs, and each move must cover either 2 stairs or 3 stairs. The order of the moves matters: taking a 2-step move followed by a 3-step move is a different route from taking a 3-step move followed by a 2-step move.

Let $a_n$ be the number of valid routes to stair $n$. The recurrence follows by sorting routes according to their final move. You can also get an explicit finite sum by choosing how many 3-step moves a route contains.

The recurrence and initial values

A route to stair $n$ must finish in one of two ways:

• Its last move covers 2 stairs, so the earlier part is a route to stair $n-2$.
• Its last move covers 3 stairs, so the earlier part is a route to stair $n-3$.

These two cases do not overlap, so for $n\ge 3$:

$$a_n=a_{n-2}+a_{n-3}.$$

Use the following starting values:

$$a_0=1,\qquad a_1=0,\qquad a_2=1.$$

The value $a_0=1$ counts the empty route: doing no moves is one way to reach the starting point. This convention makes the recurrence work at $n=3$, giving $a_3=a_1+a_0=1$. There is no route to stair 1, while stair 2 can be reached with one 2-stair move.

The first values are:

$n$	0	1	2	3	4	5	6	7	8
$a_n$	1	0	1	1	1	2	2	3	4

An explicit formula using binomial coefficients

Suppose a route contains $j$ moves of 3 stairs. Those moves cover $3j$ stairs, so the number of 2-stair moves must be

$$i=\frac{n-3j}{2}.$$

This is possible only when $n-3j$ is nonnegative and even. Once the route has $i$ moves of 2 stairs and $j$ moves of 3 stairs, it contains $i+j$ moves in total. Choose which $j$ positions contain the 3-stair moves; the remaining positions are 2-stair moves. There are $\binom{i+j}{j}$ such arrangements.

Therefore,

$$a_n=\sum_{\substack{0\le j\le \lfloor n/3\rfloor\\ n-3j\text{ is even}}}\binom{(n-3j)/2+j}{j}.$$

This finite sum gives the count directly from $n$, without generating all earlier values. For $n=0$, the sum includes $j=0$ and gives $\binom{0}{0}=1$, consistent with the empty-route convention.

Worked example: 8 stairs

For $n=8$, the possible values of $j$, the number of 3-stair moves, must make $8-3j$ nonnegative and even. This leaves $j=0$ and $j=2$.

• If $j=0$, there are four 2-stair moves. They have one arrangement: $\binom{4}{0}=1$.
• If $j=2$, there is one 2-stair move and two 3-stair moves. The three moves can be ordered in $\binom{3}{2}=3$ ways.

Thus,

$$a_8=\binom{4}{0}+\binom{3}{2}=1+3=4.$$

The four routes are $2+2+2+2$, $2+3+3$, $3+2+3$, and $3+3+2$.

Generating function and characteristic equation

The ordinary generating function is

$$A(x)=\sum_{n\ge 0}a_nx^n=\frac{1}{1-x^2-x^3}.$$

The denominator records the permitted move lengths: after any partial route, the next move contributes either $x^2$ or $x^3$. Equivalently, the recurrence has characteristic equation

$$r^3-r-1=0.$$

If an exponential-root form is useful, let $r_1,r_2,r_3$ be the three roots of this equation. Then

$$a_n=\sum_{k=1}^{3}\frac{r_k^{n+2}}{3r_k^2-1}.$$

The roots include a complex-conjugate pair, but their contributions combine to give the real integer count. The binomial sum is often the more practical explicit formula for this particular counting problem.

Common mistakes

• Allowing a 1-stair move: That is a different problem. If moves of 1, 2, or 3 stairs are allowed, the recurrence becomes $a_n=a_{n-1}+a_{n-2}+a_{n-3}$, with different initial conditions.
• Counting move totals but not their order: A route with one 2-stair move and two 3-stair moves has three arrangements, not one.
• Using the wrong initial value at zero: Taking $a_0=0$ breaks the recurrence at $n=3$. The empty route is counted as one way to cover zero stairs.
• Including impossible values of $j$: In the sum, $n-3j$ must be both nonnegative and even; otherwise the required number of 2-stair moves is not a nonnegative integer.