+5 votes

There are N steps, how many possible ways are there to climb those steps if you can take either 1 or 2 steps at a time?

1+(n-1)!/(n-2)!+(n-2)!/(n-4)!2!+(n-3)!/(n-6)!3! .....

0 votes

Thanks for the query.

Other than the way Salil Agarwal suggested in his comment there is another way to solve the above problem. If the problem is broken down it implies - how many ways can the number N be represented as sum of various '1' s and '2's. The number of '1's can vary from 0 to N and the number of '2's can vary from 0 to N/2 - if N is even and (N-1)/2 - if N is odd. **The shortcut method is the N th number of the Fibonacci series**. The Fibonacci series is - 1,2,3,5,8,13,21,34,............. where the later number is the sum of the previous two numbers of the series.

For eg. if one has to cross 6 steps, i.e., N = 6, the ways to cross 6 steps by '1's and '2's is the **6th Fibonacci number which is 13.**

**In case of 10 steps it is 89** (see my answer - http://puzzle.queryhome.com/15943/in-how-many-different-ways-you-can-climb-10-stairs)

Cheers !

...