Thread: 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 up to 9:











which gave me but I think this is wrong.

Please double-check my values for /help me solve this!

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 up to 9:











which gave me but I think this is wrong.

Please double-check my values for /help me solve this!

Your recurrence relation is correct!

Think about the last step, that takes one to the top of the staircase. It covers either the top two stairs or the top three stairs. So to climb a flight of n stairs, you either climb the first n–2 stairs, followed by a 2-stair step; or you climb the first n–3 stairs, followed by a 3-stair step. Think about the number of ways of doing that, and you'll see where the recurrence relation came from.