Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$


share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
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.
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.