# Stairs problem (recurrence)

• Sep 3rd 2009, 07:44 AM
DaRush19
Stairs problem (recurrence)
Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
Write a recurrence relation for the number of ways to ascend this staircase.
I worked out the values for [Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
Write a recurrence relation for the number of ways to ascend this staircase.

I worked out the values for $Q_{n}$ up to 9:
$Q_{0}= 0$
$Q_{1}= 0$
$Q_{2}= 1$
$Q_{3}= 1$
$Q_{4}= 1$
$Q_{5}= 2$
$Q_{6}= 2$
$Q_{7}= 3$
$Q_{8}= 4$
$Q_{9}= 5$

which gave me $Q(n) = Q(n-2) + Q(n-3)$ but I think this is wrong.

Please double-check my values for $Q_{n}$/help me solve this!
• Sep 3rd 2009, 12:43 PM
Opalg
Quote:

Originally Posted by DaRush19
Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
Write a recurrence relation for the number of ways to ascend this staircase.
I worked out the values for [Consider a staircase with n stairs which one can clim by 2 stairs or by 3 stairs at each step. e.g. a staircase with n=9 stairs can be climbed in exactly 5 ways.
Write a recurrence relation for the number of ways to ascend this staircase.

I worked out the values for $Q_{n}$ up to 9:
$Q_{0}= 0$
$Q_{1}= 0$
$Q_{2}= 1$
$Q_{3}= 1$
$Q_{4}= 1$
$Q_{5}= 2$
$Q_{6}= 2$
$Q_{7}= 3$
$Q_{8}= 4$
$Q_{9}= 5$

which gave me $Q(n) = Q(n-2) + Q(n-3)$ but I think this is wrong.

Please double-check my values for $Q_{n}$/help me solve this!