# Recursion

• Sep 16th 2008, 05:34 PM
Chief65
Recursion
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?
• Sep 16th 2008, 06:24 PM
PaulRS
Quote:

Originally Posted by Chief65
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 \$\displaystyle a_n\$ the ways of getting to the nth step.

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

There are 2 possible ways of getting there:

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

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

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