Question

Consider a flight of stairs with ? stairs. Larry Bird can take one, two or three stairs in a single stride. Find a recurrence relation for ?(?), the number of different ways that Larry Bird can traverse the stairs. Give both the initial conditions (?(1), ?(2) and ?(3)), as well as the recurrence relation for ?(?), with ? ≥ 3.

Answer 1

Let S(n) be the number of ways that Larry Bird can climb n stairs.

and He can climb one, two or three stairs in a single stride.

that is if he is on (n-3)th stair he can go to nth stair by taking 3 steps in a single stride, also if he is on (n-2)th stair he can go to nth stair by taking 2 steps in a single stride and if he is on (n-1)th stair he can go to nth stair by taking 1 step, and all these cases are mutually exclusive.

So we can see that to reach on nth stair it depends on how you reached on (n-1), (n-2) and (n-3)th stairs.

So, we can see there is a recurrence relation. S(n) = sum of cases how you reached on (n-1)th, (n-2)th and (n-3)th stairs

and these are mutually exclusive cases. So,

S(n) = S(n - 1) + S(n - 2) + S(n - 3) for n >= 3

So, now we find out the initial conditions

let we are at 0th step,

define S(0) = 1

for n = 1 only one case, 0 -> 1, So S(1) = 1

for n = 2 , 0 -> 1 -> 2 and 0 -> 2, So S(2) = 2

for n = 3, 0 -> 1 -> 2 -> 3, 0 -> 2 -> 3, 0 -> 1 -> 3 and  0 -> 3 , So S(3) = 4

So we can see that S(3) = S(2) + S(1) + S(0) = 2 + 1 + 1 = 4, true for n = 3