Recursion

Chief65 · #1 $Old$ 09-16-2008, 07:34 PM

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?

PaulRS · #2 $Old$ 09-16-2008, 08:24 PM

Quote:

Originally Posted by Chief65 $View Post$

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?

Call $a_n$ the ways of getting to the nth step.

Suppose we want to climb to the nth step, and $n\geq{2}$ .

There are 2 possible ways of getting there:

We are at the n-1 step, and we jump to the next. $a_{n-1}$ 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. $a_{n-2}$ ways of doing this

So we have $a_{n}=a_{n-1}+a_{n-2}$

Now $a_0=1$ (there's one way of doing nothing) and $a_1=1$ and our sequence is determined