# Stairs problem (recurrence)

• Sep 3rd 2009, 06: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 \$\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!
• Sep 3rd 2009, 11:43 AM
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 \$\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!