1. ## 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 $\displaystyle Q_{n}$ up to 9:
$\displaystyle Q_{0}= 0$
$\displaystyle Q_{1}= 0$
$\displaystyle Q_{2}= 1$
$\displaystyle Q_{3}= 1$
$\displaystyle Q_{4}= 1$
$\displaystyle Q_{5}= 2$
$\displaystyle Q_{6}= 2$
$\displaystyle Q_{7}= 3$
$\displaystyle Q_{8}= 4$
$\displaystyle Q_{9}= 5$

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

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

2. 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 $\displaystyle Q_{n}$ up to 9:
$\displaystyle Q_{0}= 0$
$\displaystyle Q_{1}= 0$
$\displaystyle Q_{2}= 1$
$\displaystyle Q_{3}= 1$
$\displaystyle Q_{4}= 1$
$\displaystyle Q_{5}= 2$
$\displaystyle Q_{6}= 2$
$\displaystyle Q_{7}= 3$
$\displaystyle Q_{8}= 4$
$\displaystyle Q_{9}= 5$

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

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