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(5): A new approach with no proof by lucky)

Therefore, we get the final expression:
SUM (s+1)!/(s+1)!0!, s!/(s-1)!1!, (s-1)!/(s-3)!2!, ... , ((s+2)/2)!/1!(s/2)! which is exactly the expression for the number of combinations for s+1 stairs (odd number).

If s was odd, we would have the same thing, where (s+0)!/s!0! would transform into the first member of the series s+1, i.e. (s+1)!/(s+1)!0! = 1, next we'd be pairing up members of the two series with same numerator as showed above forming the body of the series for s+1, while the last member of the series s-1, i.e. ((s-1)/2)!/0!((s-1)/2)! = 1, which could not be paired up, would transform into the last member of the series s+1, i.e. ((s+1)/2)!/0!((s+1)/2)! = 1, thus giving us the exact number of combinations for s+1 stairs.

This proves the Fibonacci approach to solving this problem.

All of this of course, translates into what Levik smartly said in just a few sentences:
If we have n stairs, then all the possible combinations would end ip in either the last skip being by 2 stairs or the last skip being by 1 stair. This means that in the first case, we can ignore the last two stairs and calculate the number of combinations for n-2 stairs, and in the second case we can ignore the last 1 stair and calculate the number of combinations for n-1 stairs. This gives us two sets of combinations that will not have any overlappings when the last skip is applied since one set will end with 2 stairs and the other with 1 stair. These two sets together give us all possible combinations for climbing n stairs which is again a Fibonacci approach.

Posted by lucky on 2002-09-07 00:34:33