3
$\begingroup$

Given staircase of length $13$ and up to $3$ steps to climb at a time, in how many ways can a person reach the top?

Suppose we are at the top $S(13)$, one can reach here in three ways and that's from $S(12)$, $S(11)$ and $S(10)$. We can climb $1$ step from $S(12)$, $2$ steps from $S(11)$ and $3$ steps from $S(10)$. Those $1$, $2$ and $3$ steps can be climbed in $S(1)$, $S(2)$ and $S(3)$, respectively.

So, shouldn't the solution to the problem be:

$$S(13) = (S(12) + S(1)) + (S(11) + S(2)) + (S(10) + S(3))$$

How can it be just $S(13) = S(12) + S(11) + S(10)$?

$\endgroup$
4
  • $\begingroup$ Break down the cases by size of the last "step". $\endgroup$
    – hardmath
    Commented Aug 2, 2016 at 15:14
  • 2
    $\begingroup$ The same (incorrect) reasoning would suggest $$S(4)=(S(3)+S(1))+(S(2)+S(2))+(S(1)+S(3))$$ Can you see why that doesn't make sense? $\endgroup$ Commented Aug 2, 2016 at 15:19
  • $\begingroup$ To follow on from @hardmath, when you say '2 steps from Step 11' you mean 'we have advanced by a double-step, and therefore came from Step 11'. Having advanced by a double-step disallows some of S(11) + S(2) because S(2) includes single-steps. $\endgroup$
    – Shai
    Commented Aug 2, 2016 at 15:37
  • $\begingroup$ I narrowed it down to S(2) with only 1 ways to reach where S(1)=1. Hence, S(2) can be reached only from S(1) making S(2)=S(1). Now I get it, why we shouldn't take the count of steps from Step1 i.e, S(2)=S(1)+S(1)=2 which is incorrect. $\endgroup$ Commented Aug 2, 2016 at 16:16

2 Answers 2

2
$\begingroup$

You have counted various histories several times. Instead convince yourself that $$S(0)=S(1)=1, \quad S(2)=2\ ,$$ and for $n\geq3$ note that the first step can be any one from $\{1,2,3\}$. It follows that $$S(n)=S(n-1)+S(n-2)+S(n-3)\qquad(n\geq3)\ ,\tag{1}$$ according to the first decision made. I suggest that you use $(1)$ recursively with pencil and paper, since the "Master Theorem" for this recursion leads to complicated expressions involving irrational and complex solutions of a third degree equation.

$\endgroup$
0
$\begingroup$

The ways have to be disjoint in order for you to add them up. When the last step is from staircase 10,11 or 12, they are disjoint cases because in one step you reach S13. What you are doing instead is: when at stair-case 10, you are including in its count, the path where you go from 10 to 11 and 11 to 13. But this is actually captured in the case where the last step was from 11.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .