Solution to 3. In how many ways can an elf climb a staircase of 15 stairs if … - Sikademy
Author Image

Archangel Macsika

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.)

The Answer to the Question
is below this banner.

Can't find a solution anywhere?

NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?

Get the Answers Now!

You will get a detailed answer to your question or assignment in the shortest time possible.

Here's the Solution to this Question

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

Related Answers

Was this answer helpful?

Join our Community to stay in the know

Get updates for similar and other helpful Answers

Question ID: mtid-5-stid-8-sqid-3334-qpid-2033