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?

(In reply to re(4): A new approach with no proof by lucky)

"SUM (n+0)!/n!0!, (n-1)!/(n-2)!1!, (n-2)!/(n-4)!2!, ... , (0+n/2)!/0!(n/2)!"

This is the expression for n being an even number.
When n is an odd number, the number of combinations would be as follows:
SUM (n+0)!/n!0!, (n-1)!/(n-2)!1!, (n-2)!/(n-4)!2!, ... , ((n+1)/2)!/1!((n-1)/2)!

If we add up the numbers of combinations for two subsequent numbers of stairs, for example s-1 and s, where s is for example even, we have the following:

SUM (s-1)!/(s-1)!0!, (s-2)!/(s-3)!1!, (s-3)!/(s-5)!2!, ... , (s/2)!/1!((s-2)/2)! + SUM (s+0)!/s!0!, (s-1)!/(s-2)!1!, (s-2)!/(s-4)!2!, ... , (s/2)!/0!(s/2)!

First we will transform the first member of the s series as follows: (s+0)!/s!0! = (s+1)!/(s+1)!0! = 1

Next we pair up the remaining members of the two series with same numerator, as follows:
(s-1)!/(s-1)!0! + (s-1)!/(s-2)!1!
(s-2)!/(s-3)!1! + (s-2)!/(s-4)!2! ...
(s/2)!/1!((s-2)/2)! + (s/2)!/0!(s/2)!.

Note that all these pairs can be expressed as follows:
a!/x!(a-x)! + a!/(x-1)!(a-x+1)! = (a+1)!/x!(a-x+1)!
(this can be proven easily if you bear in mind that (a-x+1)! = (a-x)!(a-x+1); x! = (x-1)!x; (a+1)! = a!(a+1))

(continued in the next post)

Posted by lucky on 2002-09-07 00:32:43