Let's define F(n) as the number of ways to climb a stair of n steps either one or two steps at a time.
F(0) = 1,
F(1) = 1, and
F(2) = 2
Now, let us think about a generic staircase with n steps.
Consider the last step you will take. It will either be a "single" step, if you are now at step n-1, or a "double" step if you are at n-2. (You could take a single step from n-2 to n-1, but that wouldn't be your last step in climbing the n-step stairway).
For each of the above last steps, you will have had a multitude of ways of getting to either n-1 or n-2. Actually, if you think about it, standing on n-1, you could have gotten there in F(n-1) ways. Likewise, you had F(n-2) ways to get to step n-2.
Since in each case, the next step will be your last, and there is only one way to take it, the total number of ways to reach n is
F(n) = F(n-1) + F(n-2)
This is the equasion for the Fibonacci sequence. However, the Fibonacci sequence f(n) starts with
f(1) = 1,
f(2) = 1,
f(3) = 2 etc...
Therefore,
F(n) = f(n+1), and
F(100) = f(101)
F(100) = 5,731,478,440,138,170,84,101
(That's pretty big) |
