A stairway consists of 100 steps which can be ascended by one step at a time, two steps, three steps or, by four steps.
Determine the total number of ways to ascend the staircase.
Let f(n) be the number of ways of ascending to the nth step.
f(1) = 1
The 2nd step can be reached directly, or by taking a one more step from the first step, so F(2) = f(1) + 1 = 2
The 3rd step can be reached directly, or by taking a double step from the first step, or by taking a single step from the 2nd step, so F(3) = f(1) + f(2) + 1 = 4
The 4th step can be reached directly, or by taking a triple step from the first step, or by taking a double step from the 2nd step, or by taking a single step from the 3rd step, so F(3) = f(1) + f(2) + f(3) + 1 = 8
After that, f(n) = f(n-1) + f(n-2) + f(n-3) + f(n-4)
It is very fibonnacci-like, and should be easy to compute with a spreadsheet or a computer program.
Iterative approach
