How Many Ways Can You Climb the Stairs?

If you climbed every staircase in the widget, you have a list like this. A way up is written as its moves in order, so 1 + 2 means one stair and then two.

Stairs	The ways up	How many
1	1	1
2	1 + 1, 2	2
3	1 + 1 + 1, 1 + 2, 2 + 1	3
4	1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1, 2 + 2	5
5	1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 2, 1 + 1 + 2 + 1, 1 + 2 + 1 + 1, 2 + 1 + 1 + 1, 1 + 2 + 2, 2 + 1 + 2, 2 + 2 + 1	8
6	(13 of them)	13

Look at the last column: 1, 2, 3, 5, 8, 13. It isn’t doubling (that would be 1, 2, 4, 8, 16) and it isn’t going up by the same amount each time. But each number is the sum of the two before it: 2 + 3 = 5, 3 + 5 = 8, 5 + 8 = 13.

Every way up ends with a 1 or a 2

Take the 8 ways up 5 stairs and sort them by their last move. Every climb ends either with a single stair (from stair 4) or with a double (from stair 3). Nothing else is possible.

Look at the top row in Figure 16.1. Cover the last blue hop of each and what is left is a way up 4 stairs, and you get every way up 4 stairs exactly once. In the bottom row, cover the last red hop and you get every way up 3 stairs, once each. So

$$\text{ways up 5} = \text{ways up 4} + \text{ways up 3} = 5 + 3 = 8.$$

Nothing about 5 was special. Write W(n) for the number of ways up n stairs. A climb of n stairs ends with a single stair, after one of the W(n − 1) ways up n − 1 stairs, or with a double, after one of the W(n − 2) ways up n − 2. The two groups don’t overlap (a climb can’t end with both kinds of move) and between them they hold every climb, so

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

This is the reason the pattern holds, and why it will hold for 7 stairs, 10 stairs or a thousand. A rule that gives each number of a sequence from the ones before it is called a recurrence relation, or just a recurrence, and a sequence made this way is defined recursively. The numbers 1, 1, 2, 3, 5, 8, 13, … are the Fibonacci numbers; the Grades 6–8 topic Why Do Sunflowers Count in Fibonacci Numbers? found them in the spirals of a sunflower and ended with this very staircase as a question; this page finds why the rule must hold, and where it leads.

The rule needs somewhere to start

A recurrence alone is not enough: “each number is the sum of the two before it” is just as true of 2, 1, 3, 4, 7, 11, …. To pin the sequence down you need its first two numbers, the starting values: here W(1) = 1 and W(2) = 2.

It is neater to start at 0 stairs. How many ways are there to climb no stairs? One: stand still. It sounds like a joke, but it is what the rule needs: W(2) = W(1) + W(0) = 1 + 1 = 2 is right. So the stairs’ sequence is

$$W(0) = 1, \quad W(1) = 1, \quad W(n) = W(n-1) + W(n-2) \text{ for } n \ge 2,$$

which is the very example the United States’ Common Core standards give for a sequence defined recursively. Now the table can run as far as you like, each number from the two before:

Stairs n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	20	30
Ways W(n)	1	1	2	3	5	8	13	21	34	55	89	144	233	377	10,946	1,346,269

Ten stairs: 89 ways, the answer to Sujan’s question. Thirteen stairs: 377, more than the days in a year.

A second count, to check the first

There is another way to count the 89, and getting the same answer twice is a good sign. Sort the climbs of 10 stairs by how many double moves they use. With k doubles you need 10 − 2k singles, so 10 − k moves in all, and a climb is fixed once you say which of those moves are the doubles: the number of ways to choose k places out of 10 − k. (In Grade 12 this is written ${}^{10-k}C_k$; the Grades 6–8 topic How Many Ways Can You Walk to School? finds the same numbers in Pascal’s triangle.)

Doubles k	0	1	2	3	4	5	Total
Moves	10	9	8	7	6	5
Ways to place the doubles	1	9	28	35	15	1	89

The same 89, and this table shows something the recurrence doesn’t: most ways up use two or three doubles.

One rule, many staircases

The argument didn’t really care that the moves were 1 and 2. If you may climb 1, 2 or 3 stairs at a time, a climb ends with one of three moves, so

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

In general: the ways up stair n are the sum of the ways up each stair one allowed move below it. Try it on other rules.

What the widget shows, all from that one rule:

• 1, 2 or 3 stairs at a time: 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274 ways up 10 stairs. Each number is the sum of the three before it.
• 1 or 3 stairs at a time: 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, 28 ways up 10. This list has a story of its own, below.
• 2 or 3 stairs at a time: there is no way up a single stair, so W(1) = 0. After that every staircase can be climbed, 12 stairs in 12 ways.
• Any number of stairs at a time: turn on all four moves and the counts start 1, 1, 2, 4, 8, doubling, until the stairs get taller than the longest move. If every jump were allowed, however long, they would double for ever: $W(n) = 2^{n-1}$. Here is why without any adding: between the bottom and the top lie n − 1 stairs, and a climb is fixed by which of them you land on. Each of those stairs is either landed on or not, a choice of two, n − 1 times. So doubling, the 1,024 of the first guess, is the answer to a different puzzle: one where you may jump as far as you like.

A broken stair

The seventh stair of the temple steps near Sujan’s house is cracked, so nobody steps on it. How many ways are there up 12 stairs now?

The rule still works if the broken stair gets 0 ways, but there is a quicker argument. To get past stair 7 you must stand on stair 6 and take a double to stair 8. So a climb is a way up the first 6 stairs, then that double, then a way up the 4 stairs from 8 to 12. Any first part goes with any second part:

$$W(6) \times W(4) = 13 \times 5 = 65 \text{ ways},$$

against 233 with every stair whole. Breaking one stair takes away almost three ways in four.

When the rule doesn’t apply

The last-move argument counts climbs in a given order: 1 + 2 and 2 + 1 are different climbs. Suppose instead you only care how many of each move you make, so that 1 + 2 and 2 + 1 count as one. Then the recurrence is wrong: up 10 stairs you can make 0, 1, 2, 3, 4 or 5 doubles and fill in with singles, so there are only 6 ways, not 89. Before using a rule, ask what it counts: a recurrence built by looking at the last move always counts things in order.

The stairs’ numbers turn up in problems that have no stairs in them. The trick is to turn one problem into the other, so that each answer to one becomes exactly one answer to the other.

A path of bricks. A garden path 2 bricks wide is paved with bricks twice as long as they are wide. Each brick lies either across the path or along it. How many patterns are there for a path 10 bricks long? Look at the path’s far end. Either one brick lies across it, using up 1 unit of length, or two bricks lie along it side by side, using up 2 (a single brick lying along must have its partner beside it, or the path has a gap). One unit or two: the same choice as a single or a double stair. So a path n long has W(n) patterns, and 10 long has 89.

Festival lights. For Tihar, a string of lights in a row is set so that no two bulbs next to each other are lit at the same time. How many patterns of lit and unlit bulbs are there for a string of 8? Add one extra unlit bulb at the end, and read the string from the start: every lit bulb is followed by an unlit one, so cut the string into pieces that are either “unlit” (one bulb) or “lit, unlit” (two bulbs). Each pattern of 8 bulbs becomes a climb of 9 stairs, and each climb of 9 stairs becomes a pattern. So there are W(9) = 55 patterns.

Rhythms in poetry. In Sanskrit verse a short syllable takes one beat and a long one two, so the rhythms of a line of n beats are the climbs of n stairs. That is where these numbers were first counted, centuries before Fibonacci (the Grades 6–8 topic Where Did the Missing Square Go? tells that story).

The ratio settles down

Divide each number of ways by the one before it:

n	5	6	7	8	10	15	20
W(n) ÷ W(n − 1)	1.6	1.625	1.615	1.619	1.6182	1.61803	1.61803

The ratios swing above and below, closer each time, to 1.618… So for long staircases, each extra stair multiplies the number of ways by about 1.618. Ten more stairs multiply it by about 1.618¹⁰, which is 123: that is why 20 stairs give 10,946 ways, about 123 times the 89 for 10.

Growing by the same factor each step is what a geometric sequence does (Grade 10’s GP), so try a GP in the rule. Suppose $W(n) = r^n$ for some number r. Then the recurrence says

$$r^n = r^{n-1} + r^{n-2},$$

and dividing by $r^{n-2}$ leaves a quadratic equation:

$$r^2 = r + 1, \qquad r = \frac{1 + \sqrt{5}}{2} \approx 1.618 \quad\text{or}\quad r = \frac{1 - \sqrt{5}}{2} \approx -0.618.$$

The first root is the golden ratio, written φ (the Greek letter phi); call the second ψ (psi). Both $\varphi^n$ and $\psi^n$ obey the stairs’ rule. Neither fits the stairs on its own: $\varphi^n$ starts 1, 1.618, …, but the stairs start 1, 1. A mix $a\varphi^n + b\psi^n$ obeys the rule too, because the rule only adds (add the line $a\varphi^n = a\varphi^{n-1} + a\varphi^{n-2}$ to the same line for ψ). A mix has two numbers to choose, a and b, so it can be made to fit both starting values: a + b = 1 for 0 stairs and $a\varphi + b\psi = 1$ for 1 stair. Solving these two equations gives $a = \varphi \div \sqrt{5}$ and $b = -\psi \div \sqrt{5}$. The two starting values fix the next number, that one the next, and so on, so a mix that fits the start and obeys the rule fits every staircase:

$$W(n) = \frac{\varphi^{\,n+1} - \psi^{\,n+1}}{\sqrt{5}}.$$

This is Binet’s formula, named after Jacques Binet, who found it in 1843, though Abraham de Moivre had found it already in 1718, and Daniel Bernoulli too. It is an explicit formula: it gives W(n) straight from n, without the numbers before it.

Because ψ is between −1 and 1, its powers shrink towards 0: the ψ part is already less than 0.01 at 10 stairs. So you can drop it and round: W(n) is the whole number nearest to $\varphi^{n+1} \div \sqrt{5}$. For 100 stairs that gives 573,147,844,013,817,084,101, exactly what the recurrence gives.

Each rule has its own growth factor from its own equation: for moves of 1 or 3, $r^3 = r^2 + 1$ gives about 1.4656; for 1, 2 or 3, $r^3 = r^2 + r + 1$ gives about 1.8393; for any move, 2.

Where the formula lets you down

Binet’s formula is exact, but a computer working it out isn’t: Python, JavaScript and a spreadsheet keep only about 16 significant digits of φ (ordinary “floating-point” numbers). Ask Python or JavaScript for the nearest whole number to $\varphi^{71} \div \sqrt{5}$ and both say 308,061,521,170,130. The true W(70) is 308,061,521,170,129. Every smaller staircase comes out right, but from 70 stairs on (every one up to 100, at least) the rounding errors in φ have grown bigger than the gap between whole numbers. A calculator that keeps fewer digits goes wrong sooner. The recurrence, adding whole numbers, never makes that mistake. So use the recurrence for the exact count, and the formula for how big: for 1,000 stairs it says at once that there are about $\varphi^{1001} \div \sqrt{5}$, roughly 7 × 10²⁰⁸ ways, a number of 209 digits.

• Why Do Sunflowers Count in Fibonacci Numbers? (Grades 6–8) The same numbers in the spirals of a flower, and the golden angle.
• How Many Ways Can You Walk to School? (Grades 6–8) Counting routes by adding, and Pascal’s triangle, where the table of doubles came from.
• Is the Golden Ratio Really Everywhere? The 1.618 of this page: where it truly appears, and where the claims are made up.
• How Many Moves to Move 64 Disks? (Computing, Going Further) Another recurrence, M(n) = 2M(n − 1) + 1, and the doubling it leads to.
• Grade 11 Computing: Recursion or a loop? The stairs as a program, and why the obvious one is so slow.
• Grade 12 Computing: Dynamic programming Counting small cases once and building up, the idea behind autocorrect.
• Grade 10 Math: Sequence and Series Arithmetic and geometric sequences, the patterns this page started from.