Question

An elf has a staircase of n stairs to climb. each step it takes can be 1 or 3 stairs. Find a recurrence relation for A_n, the number of different ways for the elf to ascend the n-stair staircase.

Answer 1

SOLUTION :

Given that ,

Total number of stairs = n

The elf can take 1,2 or 3 steps: Number of ways to take each step = 3

Lets say in the process he took

• A number of 1 steps
• B number of 2 steps
• C number of 3 steps

Total steps is equal to :

Hence the number of possible ways is the total number of possible solutions to this equation with A,B,C being whole numbers.

So to find recurrence relation, we can substitute various values for n,

n = 1:

possible solutions:

We should also take the permutations of these solutions : 1

n = 2:

possible solutions:

We should also take the permutations of these solutions : 2

n = 3:

possible solutions:

We should also take the permutations of these solutions : 1+2+1 = 4

n = 4:

possible solutions:

We should also take the permutations of these solutions : 1+1+3+2 = 7

n = 5 :

possible solutions:

We should also take the permutations of these solutions : 1+3+4+3+2 = 13

n = 6 :

possible solutions:

We should also take the permutations of these solutions : 1+5+4+6+6+1+1 = 24

What we should observe that the number of ways is always of the form:

because the number of ways of taking the total steps is just the number of ways of taking previous steps plus number of ways of taking the extra new steps which can be either one two or three.

So we get:

• a(1) = 1
• a(2) = 2
• a(3) = 4
• a(4) = 7 = 4+3+2
• a(5) = 13 = 7+4+2
• a(6) = 24 = 13+7+4
• a(7) = 24+13+7 =44....

Hence we have discovered and verified the sequence.

--------------------- the end --------------------