1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Is this from the AMC 8 (because it seems familiar)? $\endgroup$ – pidude Jul 15 '14 at 15:50
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.