# 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
yes I used this method at first but what if I don't have Wolfram at hand? is there any other way? –  tenam Jan 10 '12 at 17:14
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

In turn.

1. Call $c_n$ the number of ways to climb $n$ stairs. The last step is of length 1, 2, or 3, so the total is: $$c_n = c_{n - 1} + c_{n - 2} + c_{n - 3}$$
2. As starting points, $c_0 = 1$ (one way to do nothing), $c_1 = 1$ (one way, one step), $c_2 = 2$ (two ways, either two one-steps or one two-step).
3. Left as an exercise in stair-climbing ;-)
4. Take a constant $C$, to be determined later, and assume that for some $a$: $$c_n \ge a \cdot C^n$$ Replacing in the recurrence: $$a \cdot C^n \ge a \cdot C^{n - 1} + a \cdot C^{n - 2} + a \cdot C^{n - 3}$$ The tightest we can do is to take $C$ as the largest root of: $$x^3 - x^2 - x - 1 = 0$$ We see that $1 < C < 2$, so the sequence certainly increases exponentially. To get $a$, pick some $c_{n_0} = a \cdot C^{n_0}$ and work from there. Simple is $n_0 = 1$, which gets $c_n \ge C^{n - 1}$. To prove this by induction is left as another stair-climbing exercise.
-