# Solving recursions with combinatorics

A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3 steps at a time. Count how many possible ways the child can run up the stairs.

This is a problem on Cracking the Code Inteview but I'm wondering if there's a way to solve this with combinatorics; essentially directly calculate the answer without dynamic programming.

• You may need to solve $x^3-x^2-x-1=0$ – Henry Jul 13 '17 at 20:54

## 1 Answer

You can certainly solve the recurrence explicitly. If $A(n)$ is the ordered number of ways to sum to $n$ using $1,2,3$ we have $A(n)=A(n-1)+A(n-2)+A(n-3)$, the Tribonacci numbers but offset by $2$ because in your case A(0)=$A(1)=1$. They are given in OEIS A000073. There are various forms of a closed form solution given. The usual approach to homogeneous recurrence relations applies, assume a solution of the form $r^n$. Plugging that in gives $r^3=r^2+r+1$, which has three roots $r_1,r_2,r_3$. The general solution is $ar_1^n+br_2^n+cr_3^n$. You find $a,b,c$ from the initial conditions.