Home > Problem of the Week > Archive List > Detail

 << Prev 7/31/2005 Next >>

## Climbing Stairs

Suppose you are running up a staircase that involves thirteen steps (i.e. thirteen is the standard number for most home staircases).

You can take either one or two steps at a time.

How many different ways is it possible to run up the staircase?

What if the stairs has n-steps?

Note 1: Order is important, so treat the sum 1+2+1+1+1... as different from the sum 1+1+2+1+1....

Note 2: Do you have to worry about the last step?

Hint: The more complicated approaches lie in trying to list all of the cases for thirteen steps by exhaustion...or even to try to invoke the power of combination formulae.

Students find the best approach is to reduce the problem and systematically explore the cases of one-step, two-step, three-step, etc. staircases.

Be prepared for a surprise.

Solution Commentary: Lets look at the data:

• One-step: 1 way {1}
• Two-steps: 2 ways {1+1, 2}
• Three-steps: 3 ways {1+1+1, 2+1, 1+2}
• Four-steps: 5 ways {1+1+1+1, 2+1+1, 1+2+1, 1+1+2, 2+2}
Do you see a familiar pattern forming...leading to an answer of 233 ways for a thirteen-step staircase?

Can you see why this familiar pattern is occurring (e.g. think about a famous rabbit problem)...analyze the four step staircase options in light of the options for the two-step and three-step staircases?

Note: For those who want to explore a great generalization of this problem to n-step staircases using integral steps of size 1, 2, ... r (for r < n+1), browse through Mohammad Azarian's "A Generalization of the Climbing Stairs Problem" (Mathematics and Computer Education, Winter 1997, pp. 24-28).