How do you set up this recursive system?

Question

Here is the problem:

Emma wants to climb a 12-step staircase. She can climb either 1 or 2 steps at a time. In how many ways can she climb the staircase?

I first set $F_{n}$ as the number of steps it takes to get to $n$ stairs. To get from the $n-2$ step to $n$, you can either take 2 single steps or 1 double step. So, it would seem like $F_{n}=2\cdot F_{n-2}$. We know $F_{1}$ is 1 and $F_{2}$ is 2, but the recurrence doesn't work as $F_{3}$ is 3. The real solution is that because the last step can either be 1 or 2 steps, we know that $F_{n}=F_{n-1}+F_{n-2}$. Can someone explain what was wrong with my bogus solution?

Answer 1

Your wrong solution does not take into account the fact that you might never be at step $n-2$ because you were at step $n-3$ and advanced by $2$.

Answer 2

For a stair of $s$ steps one can reach the first step in $W_1=1$ way and the 2nd step in $W_2=2$ ways (considering the compositions of 1 and 2 in parts of 1 or 2). For the general case one can reach step $s$ from step $s-1$ by a single step or from step $s-2$ by a single step, $W_s=W_{s-1}+W_{s-2}$. Obviously that is a fiboncacci recurrence with $W_i=F_{n+1}$. From https://oeis.org/A000045 we find $W_{12}=F_{13}=233$.