 745
 31
 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 Googlesearched: ##s_n=s_{n1}+s_{n2}##.
(a) Okay, so if Tom climbs the first step, then he has ##n1## steps to climb. So the number of ways to climb ##n## steps given he has initially climbed one, is ##s_n=s_{n1}##.
(b) Similarly, ##s_n=s_{n2}##.
(b) Similarly, ##s_n=s_{n2}##.