We just finished induction and are now starting on Recursive functions. The assigned problem is: How many ways is it possible to climb a staircase ifnsteps if one is allowed to take either one or two steps at a time?

Printable View

- September 16th 2008, 06:34 PMChief65Recursion
We just finished induction and are now starting on Recursive functions. The assigned problem is: How many ways is it possible to climb a staircase if

*n*steps if one is allowed to take either one or two steps at a time? - September 16th 2008, 07:24 PMPaulRS
Call the ways of getting to the nth step.

Suppose we want to climb to the nth step, and .

There are 2 possible ways of getting there:

- We are at the n-1 step, and we jump to the next. ways of doing this, since we have to get to the n-1 step
- We are at the n-2 step, and we jump directly to n. ways of doing this

So we have

Now (there's one way of doing nothing) and and our sequence is determined (Wink)