Ways to climb up $9$ stairs taking $1, 2$, or $3$ steps at a time When I run up a staircase, my stride can carry me up $1$, $2$, or $3$ steps at a time. In how many ways can I run up a $9$-step staircase (given that my last stride lands me on the $9^{\text{th}}$ step)? I can't do constructive and that's all I know.

Let $W_n$ the number of ways for climbing a stair with length $n$ with steps having size $\in\\{1,2,3\\}$.
We clearly have $$ W_1 = 1,\qquad W_2= 2,\qquad W_3=4 $$ and since the last step may only be $+1,+2$ or $+3$, for any $n\geq 4$ we have: $$ W_{n} = W_{n-1}+W_{n-2}+W_{n-3}.$$ Now see tribonacci numbers. We have $W_9=\color{red}{149}$.