Here's the problem:
1.Find a recurrence relation for the number of ways to climb n stairs if the person climbing the stairs can take one, two, or three steps at the time.
2.Explain how the relation is obtained
3.What are the initial condition (base case)
4.How many ways can this person climb a flight of nine stairs
5.Show that this number is an exponential function of n. That is, find a real constant $c > 1$ such that this number is at least $c^n$.
I know the recurrence formula is $C_n = C_{n-1} + C_{n-2} + C_{n-3}$, but for question five, I used induction to show $C_n >= c^n$ for some constant c, but
$C_n >= c^{n-1} + c^{n-2} + c^{n-3} >= c^n * (1/c + 1/c^2 + 1/c^3)$
since $1/c + 1/c^2 + 1/c^3$ is a less than 1 for $c > 1$, I don't know how $C_n$ is guaranteed $>= c^n$
Thanks!