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!