Part (a): Climbing the stairs
Let’s denote by an the number of different ways Alex can climb a staircase with n steps, given that at each move he may go up either 1 step or 2 steps.
We can reason recursively:
- To reach step 1, there's only 1 way — a single 1-step move. So a₁ = 1.
- To reach step 2, there are 2 ways: either (1 + 1) or (2). So a₂ = 2.
For any n > 2, Alex can reach the top in one of two ways:
- By first climbing 1 step, and then climbing the remaining n − 1 steps — there are an−1 such ways.
- By first climbing 2 steps, and then climbing the remaining n − 2 steps — there are an−2 such ways.
This gives the recurrence relation:
an = an−1 + an−2
This is the Fibonacci sequence starting from a₁ = 1 and a₂ = 2. Calculating up to n = 10:
- a₃ = 3
- a₄ = 5
- a₅ = 8
- a₆ = 13
- a₇ = 21
- a₈ = 34
- a₉ = 55
- a₁₀ = 89
Answer: Alex can climb the staircase in 89 different ways.
Part (b): Descending the stairs
Now suppose Alex is jumping down the same staircase. He is allowed to jump over any number of steps, including jumping all the way from the top to the ground in one move.
We can think of the staircase as having 9 gaps between the 10 steps. At each of these 9 positions, Alex can make a binary choice:
- Jump over the step (i.e. don't land there)
- Land on the step
Each sequence of decisions corresponds to a unique descent path. Since each of the 9 gaps has 2 options, the total number of descent patterns is:
2⁹ = 512
Answer: Alex can descend the staircase in 512 different ways.
