Climbing ten steps one or two at a time

Question

A staircase has 10 steps. With each stride you climb either 1 step or 2 steps. Two ways of climbing count as different if the sequence of strides is different (so 1-2 and 2-1 are different ways of climbing three steps). How many different ways are there to climb the ten steps? Explain the pattern that makes the count easy.

Accepted Answer

89 ways. The recursion. Let W(n) be the number of ways to climb n steps. Every way of climbing n steps ends with a stride of 1 (preceded by some way of climbing n minus 1 steps) or a stride of 2 (preceded by some way of climbing n minus 2 steps). These two groups do not overlap and cover everything, so W(n) = W(n minus 1) + W(n minus 2). With W(1) = 1 (a single step) and W(2) = 2 (1-1 or 2), the sequence runs 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. So W(10) = 89. These are the Fibonacci numbers, shifted by one place. It is the standard first example of how a "count the ways" question turns into a …

Climbing ten steps one or two at a time

Your answer

Discussion

Learn the concepts

Related questions