0
$\begingroup$

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!

  • 0
    You have $C_n\geq C_{n-1}+C_{n-2}$; so your $C_n$ increase at least as fast as the Fibonacci numbers.2012-01-10

2 Answers 2

1

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.

  • 0
    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$2012-01-10
0

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.