In how many ways can a boy climb a staircase of 10 steps if, at each move, he…

Concept: If f(n) is the number of ways to reach the n-th step when each move is either 1 step or 2 steps, then the last move to reach step n is either a single 1-step from step (n − 1) or a single 2-step from step (n − 2). So f(n) = f(n − 1) + f(n − 2) — the same recurrence as the Fibonacci sequence, with base cases f(1) = 1 (one way: a single 1-step) and f(2) = 2 (either two 1-steps, or one 2-step).

Application — building the sequence term by term up to the 10th step:

1. f(1) = 1

2. f(2) = 2

3. f(3) = f(2) + f(1) = 2 + 1 = 3

4. f(4) = f(3) + f(2) = 3 + 2 = 5

5. f(5) = f(4) + f(3) = 5 + 3 = 8

6. f(6) = f(5) + f(4) = 8 + 5 = 13

7. f(7) = f(6) + f(5) = 13 + 8 = 21

8. f(8) = f(7) + f(6) = 21 + 13 = 34

9. f(9) = f(8) + f(7) = 34 + 21 = 55

10. f(10) = f(9) + f(8) = 55 + 34 = 89

Cross-check — an independent counting method: group the ways by how many 2-steps, k, are used in the climb (0 ≤ k ≤ 5, since each 2-step covers 2 of the 10 units). Using k two-steps leaves (10 − 2k) one-steps, so the climb has (10 − k) moves in total, and the number of ways to place the k two-steps among those moves is the combination C(10 − k, k):

Total = 1 + 9 + 28 + 35 + 15 + 1 = 89, matching the recurrence method above. So the boy has 89 distinct ways to reach the top of the 10-step staircase.