In how many ways can you walk up a stairway with 6 steps if you
can take one or two steps at a time? (For example, you can walk up
a stairway with 3 steps in three dierent ways: (i) Take three single
steps. (ii) Take one step and then two steps. (iii) Take two steps and
then one step.)
Select:	A) 9	B) 10	C) 11	D) 12	E) 13
Let fn denote the number of ways one can get to the nth step. Given the example   in the problem, we see then that f3 = 3. It is easy to see f1 = 1 and f2 = 2 (the latterfollows since one can take one step twice or two steps at a time to get to the second step).   To determine the value of fn for any n &gt;/3, think about the previous step a person would   have to be on before getting to the nth step. Since only one or two steps are allowed at a   time, the person would have to be either on the (n-1)st step or the (n-2)nd step there are by definition fn-1 ways someone can get to the (n - 1)st step and fn􀀀-2 ways a   person can get to the (n - 2)nd step, there must be fn-1 + fn-2 ways of getting to the   nth step (by first going to the (n- 1)st step in one of fn-1 ways and then taking a single   step or by first going to the (n-2)nd step in one of fn-2 ways and then taking two steps   at once). In other words, fn = fn-1 +fn-2. This allows us to easily compute fn for n&gt;/3   successively. Specifically,   f3 = f2 + f1 = 2+1= 
<gadget id="calculator">2+1</gadget>
<output>3</output>
3 (as we knew); f4= f3 + f2 = 3+2= 
<gadget id="calculator">3+2</gadget>
<output>5</output>
5;   f5= f4 +f3 = 5+3= 
<gadget id="calculator">5+3</gadget>
<output>8</output>
8; and f6= f5 + f4 = 8+5= 
<gadget id="calculator">8+5</gadget>
<output>13</output>
13:   Therefore, the answer is 13.   correct answer is 13
<result>E</result>
In how many ways can you walk up a stairway with 6 steps if you
can take one or two steps at a time? (For example, you can walk up
a stairway with 3 steps in three dierent ways: (i) Take three single
steps. (ii) Take one step and then two steps. (iii) Take two steps and
then one step.)