Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.