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!, (n1)!/(n2)!1!, (n2)!/(n4)!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!, (n1)!/(n2)!1!, (n2)!/(n4)!2!, ... , ((n+1)/2)!/1!((n1)/2)!
If we add up the numbers of combinations for two subsequent numbers of stairs, for example s1 and s, where s is for example even, we have the following:
SUM (s1)!/(s1)!0!, (s2)!/(s3)!1!, (s3)!/(s5)!2!, ... , (s/2)!/1!((s2)/2)! + SUM (s+0)!/s!0!, (s1)!/(s2)!1!, (s2)!/(s4)!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:
(s1)!/(s1)!0! + (s1)!/(s2)!1!
(s2)!/(s3)!1! + (s2)!/(s4)!2! ...
(s/2)!/1!((s2)/2)! + (s/2)!/0!(s/2)!.
Note that all these pairs can be expressed as follows:
a!/x!(ax)! + a!/(x1)!(ax+1)! = (a+1)!/x!(ax+1)!
(this can be proven easily if you bear in mind that (ax+1)! = (ax)!(ax+1); x! = (x1)!x; (a+1)! = a!(a+1))
(continued in the next post)

Posted by lucky
on 20020907 00:32:43 