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.
I did the same as Steve and constructed the recursive formula f(n+4) = f(n+3)+f(n+2)+f(n+1)+f(n). Simply iterating that formula with initial conditions f(1)=1, f(2)=2, F(3)=4, f(4)=8 is enough to get the answer of f(100) = 17943803336550012914104102513.
But I wanted something like a closed form that doesn't need to be iterated 96 times to get to the 100th term.
So given our recursion, it has a characteristic polynomial of x^4=x^3+x^2+x+1. A closed form solution will consist of powers of the roots multiplied by some coefficients. So then the roots are x~1.927562, x~-0.774804, x~-0.076379+/-0.814704.
Notice that three of those roots obey the inequality 0<abs(x)<1. So when evaluating for large n they tend towards zero. This means that we can efficiently approximate f(n) with just the single larger root: c*1.927562^n for some constant c.
In this case c=0.566344 is our constant. So lets test it out with n=10: 0.566344*1.927562^10 = 401.018. This is extremely close to the explicitly calculated value of 401. So then 0.566344*1.927562^100 = 1.794386*10^28. This does correlate to the exact value of 17943803336550012914104102513 for the first six digits. In this case my estimation formula f(n) ~= 0.566344*1.927562^n does not have enough precision in the fixed constants to get a perfectly accurate value.
I also compared this to the OEIS at sequence A000078, like Jer did. Scrolling down, one of the comments has a much more precise set of constants.
OEIS: "a(n) ~ c*r^n, where c = 0.079077767399388561146007... and r = 1.92756197548292530426195..."
Taking into account the OEIS has a different offset for the sequence start then my f(n) ~= 0.079077767399388561146007 * 1.92756197548292530426195^(n+3)
Solution
