Number of ways of walking up $6$ steps taking $1, 2,$ or $3$ at a time, and a recurrence relation

Question

Suppose you want to walk up a staircase of $6$ steps, and can take $1, 2$ or $3$ steps at a time. How many ways are there to walk the $6$ steps?

It seems hard to count the number of ways of walking the steps directly, but on second thought we can find a relation between the number of ways of walking $n$ steps with the number of ways of walking fewer steps: To get to n steps, one must get to $n-1, n-2$ or $n-3$ steps before the last hop. If one can get to $n-1, n-2$ or $n-3$ steps, there is exactly one way to complete the $n$-step walk. Thus if $a_n$ denotes the number of ways of walking $n$ steps, we have $a_n = a_{n-1} + a_{n-2} + a_{n-3}$ for $n\geq 4$.

I randomly came along with the above passage but I have a question: why the recurrence relation is not $a_n= a_{n-1}+ 2a_{n-2}+ 4a_{n-3}$ instead?

My thinking is, when one get to $n-1$ steps, then one have no choice but to take $1$ last step. But if one get to $n-2$ steps, then one have two choices, namely taking $2$ steps at once or two $1$-step, hence the coefficient $2$ in the $a_{n-2}$. Likewise, if one get to $n-3$ steps, then we have 3 choices: $111, 12, 21, 3$.

Can anyone explain?

Answer 1

The breakdown into cases is based on what the last step is. The only possibilities are that it is a $1$, a $2$, or a $3$. These three possibilities are disjoint.

If the last step is a $1$, we must have arrived at $n-1$ before taking that last step, and there are $a_{n-1}$ ways to do that. A similar analysis counts the paths with last step a $2$, and the ones with last step a $3$.

Answer 2

The point is suppose you taped a person going back in time and going up the $n$ stairs in each way possible. What you are doing is going back in time one step. This will give you a bijective function from all the ways to go up $n$ steps to all the ways to go up $n-3, n-2$ or $n-1$ steps.

Notice what you propose counts some ways twice.

Answer 3

In your own try, $$a_n= a_{n-1}+ 2a_{n-2}+ 4a_{n-3}$$ you count some cases twice:
When you take two steps at once, you get one $a_{n-2}$. When, coming from $a_{n-2}$ you take one step twice, you go via $a_{n-1}$, and thus that possibility is counted in $a_{n-1}$ and you don't have to include $a_{n-2}$ twice to get $a_{n}$.