• Support PF! Buy your school textbooks, materials and every day products via PF Here!

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

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

andrewkirk

Science Advisor
Homework Helper
Insights Author
Gold Member
3,715
1,344
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'.
 
So I just add the two answers togther?
 
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)?" You must log in or register to reply here.

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
Top