# 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?

+5 votes
360 views
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?
posted Oct 23, 2013
Share this puzzle

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

## 1 Answer

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 !

answer Jul 29, 2016

Similar Puzzles
+1 vote

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?

+2 votes

When rolling 10 dice with 2020 faces each (numbered 1 to 20), how many ways are there of rolling a total sum of 15?

+1 vote

Total cost of 1 kg apple, 1 kg grape and 2 kg banana is 210 Rupees.

If cost of fruits are in the order as given below
Cost of banana (1kg) =< Cost of grape (1kg) =< Cost of apple (1kg)
and all costs are multiple of 10 Rupee and minimum and maximum cost of any fruit per Kg is ranging from 30 Rupees to 90 Rupees.

How many total number of possible cases are there and which are those?