Understanding the step-hop problem mathematically I am working on a problem where one is given n number of steps. They can take either one, two, or three steps. How many number different possible ways are there to climb the n steps?
I can solve this problem recursively, using a decision tree, but I'm having a really hard time understanding how to solve it using math. 
Is there an analytical way or combinatorial to solve this? (Or any other way beyond programming).
 A: These numbers are described by a simple recurrence: if $a_n$ is the number of ways to climb $n$ steps, then $a_0=1$, $a_1=1$, $a_2=2$, and for $n\ge 3$ we have
$$a_n=a_{n-1}+a_{n-2}+a_{n-3}\;.\tag{1}$$
To see this, note that if the first step goes up $1$, there are $a_{n-1}$ ways to finish the climb, if it goes up $2$ there are $a_{n-2}$ ways to finish the climb, and if it goes up $3$, there are $a_{n-3}$ ways to finish the climb. These are the only possibilities, and they obviously don’t overlap, so we get the recurrence $(1)$. 
There are standard ways to get a closed form from $(1)$ and the initial values. Alternatively, we can use them to calculate a few terms and then consult The On-Line Encyclopedia of Integer Sequences as a shortcut. We have:
$$\begin{array}{rcc}
n:&0&1&2&3&4&5&6&7\\
a_n:&1&1&2&4&7&13&24&44
\end{array}$$
Searching in OEIS, we get, five returns, of which the first is clearly the one that we want: this is OEIS A000073, the sequence of what are often called Tribonacci numbers. In the FORMULA section we find that
$$a_n=\left\{\frac3{a^2+b^2+4}\left(\frac{a+b+1}3\right)^{n+2}\right\}\;,$$
where $a=\left(19+3\sqrt{33}\right)^{1/3}$, $b=\left(19-3\sqrt{33}\right)^{1/3}$, and $\{x\}$ denotes the integer nearest to $x$.
