15. [9] A cat is going up a stairwell with ten stairs. However, instead of walking up the stairs one at a time, the cat jumps, going either two or three stairs up at each step (though if necessary, it will just walk the last step). How many different ways can the cat go from the bottom to the top?
Answer: 12 The number of ways for the cat to get to the $i$ th step is the number of ways for the cat to get to step $i-2$ plus the number of ways to get to step $i-3$, because for each way to get to step $i$, we can undo the last move the cat made to go back to one of these two steps. The cat can get to step 1 in 0 ways, to step 2 in 1 way, and to step 3 in 1 way. Now we repeatedly use our formula for calculating the number of ways to get to the $i$ th step to see that the cat gets to:
\begin{tabular}{c|c|c|c|c|c|c|c|c|c|c|} 
Step & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline Number of ways & 0 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \\
\hline
\end{tabular}

So our answer is $5+7=12$.