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?

Question

You need to climb ten stairs. At every stair, you can either take one step up or you can jump two steps up.

In how many different ways you can climb 10 stairs?

Answer 1

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 !