Answer to Question #167778 in Discrete Mathematics for RV

Question

3. In how many ways can an elf climb a staircase of 15 stairs if each step it takes can cover 1 or 2 or 3 stairs? Explain why your solution is valid. (Hint: Work on fewer number of stairs first and try to generalize.) 

Answer 1

A recurrence relation for the number of ways to climb n stairs:

S(n) = S(n-1) + S(n-2) + S(n-3), where S(-2) = S(-1) = 0, S(0) = 1;

It's possible to calculate S(15) by sequential counting. S(2) = 2, S(3) = 4, S(4) = 7, S(5) = 13, ... S(15) = 5768

It's also possible to calculate it with python code:

def findStep( n) :
    if (n == 1 or n == 0) :
        return 1
    elif (n == 2) :
        return 2
     
    else :
        return findStep(n - 3) + findStep(n - 2) + findStep(n - 1) 
 
 
n = 15
print(findStep(n))  

So we can find S(15) = 5768