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

#### Eclair_de_XII

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

Related Calculus and Beyond Homework News on Phys.org

#### andrewkirk

Science Advisor
Homework Helper
Gold Member
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"?

### Want to reply to this thread?

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

### Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving