## Climbing Stairs

#### Problem

It is possible to climb three steps in exactly four different ways.

How many ways can you climb ten steps?

#### Solution

If there are ten steps, it is necessary to arrive at the 10th step, but all the other steps in between are optional.

Step Number 1 2 3 4 5 6 7 8 9 10 0 0 0 1 0 1 0 0 0 1

So the binary sequence, 0001010001, represents a journey using steps 4, 6 and 10. To find the total number of ways of climbing 10 steps we need to consider how many binary sequences can be made using 9 binary digits (as step 10 must always be a 1).

Hence there are 2^{9} = 512 ways of climbing ten steps.

What if the maximum number of steps you can climb at a time is two?

Problem ID: 74 (Apr 2002) Difficulty: 2 Star