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 $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!

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 $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!