- #1

Eclair_de_XII

- 1,083

- 91

- Homework Statement
- Tom wants to climb ##n## steps. He can either climb one step at a time, or two steps at a time.

(a) How many ways are there for him to climb ##n## steps if he initially takes one step?

(b) How many ways are there if he initially takes two steps?

(c) Use these two answers in order to derive a recurrence relation for ##s_n##, the number of ways to climb ##n## steps.

- Relevant Equations
- The answer to (c) as Google-searched: ##s_n=s_{n-1}+s_{n-2}##.

(a) Okay, so if Tom climbs the first step, then he has ##n-1## steps to climb. So the number of ways to climb ##n## steps given he has initially climbed one, is ##s_n=s_{n-1}##.

(b) Similarly, ##s_n=s_{n-2}##.

(b) Similarly, ##s_n=s_{n-2}##.