How many ways are there to to climb n steps (recurrence relations)?

[Eclair_de_XII]

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}$.

 

[andrewkirk]

The words you have written are correct but the equations are not. $s_n$ represents the number of ways to climb n steps, not the number of ways to climb n steps when the first step is 1, nor the number of ways to climb n steps when the first step is 2. So you need to delete the characters "$s_n=$" from your answers.

The recurrence relation is what you have already written under 'Relevant Equations'.

 

[Eclair_de_XII]

So I just add the two answers togther?

 

[Eclair_de_XII]

Err, how do you mark this thread as "solved"?