Contact Us!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.

| Download
Views: 149
Image: ubuntu2004
Tweet
Share
Share
Kernel: Python 3 (system-wide)

Suppose that you can walk up a set of stairs using steps of size 1, 2 and 4. In how many ways can you walk up a set of 20 stairs? Let ana_n = number of ways to n stairs using steps of size 1, 2 and 4

We know that a1a_1 = 1 and a2a_2 = 2 because we can climb in many different ways: [1] and [1,1],[2] respectively

We will compute the sum of our ways to climb using the Fibonacci Sequence formula. We will get a(n−4)+a(n−2)+a(n−1)a(n-4)+a(n-2)+a(n-1) since we can climb up using steps of size 1,2, and 4.

def a(n):
    if n == 1 or n == 0:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 3 #Since we have 3 outcomes: [2+1],[1+1+1],[1+2]
    elif n == 4:
        return 6 #Since we have 6 outcomes: [4],[2+2],[2+1+1],[1+1+1+1],[1+2+1],[1+1+2]
    else:
        return a(n-4)+a(n-2)+a(n-1)

a(20)
46754

This way, we found in how many ways we can walk up a set of 20 stairs. We can climb a set of 20 stairs in 46754 ways.