A stairway has 100 steps. You can climb it by one step at a time, or by two steps. How many different ways to ascend this stairway exist?

The solution is too large for my spreadsheet, I'll tell you what, but I am assuming I can do, two steps once or up to 50 times, and the rest ones. The rest, or number of single steps, comes out to 100-(2n) where n is the number of times I took two steps. So for every n, there are (100 - 2n) + n spots for which you can have any combination, i.e. combination 100-n chose 2. So there is a combination of 100-n choose n for n = 0 to 50.

That comes out to 573,147,844,013,817,000,000

Posted by Lawrence on 2003-08-27 14:24:48