# a simple recurrence problem

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!

-
You have $C_n\geq C_{n-1}+C_{n-2}$; so your $C_n$ increase at least as fast as the Fibonacci numbers. –  Christian Blatter Jan 10 '12 at 18:50
There is a discussion of solving these relations in Wikipedia. You form the characteristic polynomial by assuming the solution is of the form $r^n$, so in your case it is $r^3=1+r+r^2$. As one of the roots is greater than $1$, it will come to dominate. You can choose any $c$ less than this root.
how to solve $r^3-r^2-r-1=0$ by hand? we haven't covered complex number yet –  tenam Jan 10 '12 at 16:49
As the root (from Alpha) is about 1.83939, you can just check that the sign changes somewhere between $\frac32$ and $2$ and use $c=1.3$. You don't need the root itself, just a bound. –  Ross Millikan Jan 10 '12 at 17:11
You can see the sign change by hand, which is why I suggested easy numbers to calculate with. The LHS is positive at r=2 and negative at 1.5. Maybe $\sqrt 2$ is even easier: $2\sqrt 2 -2 - \sqrt 2 -1 \lt 0$ –  Ross Millikan Jan 10 '12 at 17:19