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 9th step)?
Let \(T_n\) be the number of ways to climb n stairs taking only 1 or 2 or 3 steps:
\(\begin{array}{|rcll|} \hline T_n &=& \mathcal{T}_{n+2} \qquad \mathcal{T} \text{ is the Tribonacci number } \\\\ && \text{case of n=9 steps}: \\\\ T_{9} &=& \mathcal{T}_{11} \qquad \\ && \mathcal{T}_0 = 0 \\ && \mathcal{T}_1 = 0 \\ && \mathcal{T}_2 = 1 \\ && \mathcal{T}_3 = 1 \\ && \mathcal{T}_4 = 2 \\ && \mathcal{T}_5 = 4 \\ && \mathcal{T}_6 = 7 \\ && \mathcal{T}_7 = 13\\ && \mathcal{T}_8 = 24\\ && \mathcal{T}_9 = 44\\ && \mathcal{T}_{10} = 81\\ && \mathcal{T}_{11} = 149\\ && \mathcal{T}_{12} = 274\\ && \ldots \\ T_{9} &=& 149 \\ \hline \end{array}\)
Source: http://oeis.org/search?q=1%2C2%2C4%2C7%2C13%2C24%2C&sort=&language=english&go=Search
"Tribonacci numbers: \(a(n) = a(n-1) + a(n-2) + a(n-3) \text{ with } a(0)=a(1)=0, a(2)=1\)."
"a(n) = number of compositions of n-2 with no part greater than 3.
Example: a(5)=4 because we have \(1+1+1 = 1+2 = 2+1 = 3\).
\(\ldots\)
\(a(n+1) = \dfrac{3*c*\left((1/3)*(a+b+1)\right)^n}{c^2-2*c+4}\) where
\(a=(19+3*\sqrt{33})^{1/3}\),
\(b=(19-3*\sqrt{33})^{1/3}\),
\(c=(586+102*\sqrt{33})^{1/3}\).
Round off to the nearest integer."
Example:
\(\begin{array}{|rcll|} \hline T_{9} = a(11)& =& \dfrac{3*c*\left((1/3)*(a+b+1)\right)^{10}}{c^2-2*c+4} \\ a=(19+3*\sqrt{33})^{1/3}& =& 3.30905647997\ldots \\ b=(19-3*\sqrt{33})^{1/3}& =& 1.20880378568\ldots \\ c=(586+102*\sqrt{33})^{1/3}& =& 10.5431194025\ldots \\ T_{9} & =& \frac{3*10.5431194025*\left((1/3)*(3.30905647997+1.20880378568+1)\right)^{10}}{10.5431194025^2-2*10.5431194025+4} \\ & =& \frac{14,014.7325577}{94.0711279297} \\ & =& 148.980169220 \\ \mathbf{T_{9}} & \mathbf{=}& \mathbf{149} \\ \hline \end{array} \)