There is A staircase having n steps (odd or even). A person standing at the base Can take one or two-steps at a time. My query is in how many ways can The stairs can be climbed?

SIGMA (n-x){B}C{/B}(x) where x ranges from 0 to n/2 when n is even 0 to (n-1)/2 when n is odd

nCr is nothing but the number of combinations of n different things taken r at a time, which = n!/(n-r)! r!

Ex 1: n=5 since n is odd x ranges from 0 to (5-1)/2 i.e., from 0 to 2 applying the above formula, answer is 5C0 + 4C1 + 3C2 = 1 + 4 + 3 = 8 ways

Ex 2: n=8 x ranges from 0 to 4 answer is 8C0 + 7C1 + 6C2 + 5C3 + 4C4 = 1 + 7 + 15 + 10 + 1 = 34 ways

murali

Aug 22nd, 2005

nC1+nC2

G.R.Venkatesh

Sep 9th, 2005

only one way by steping in stairs

pramod

Sep 12th, 2005

the person can go in two steps

PALLAV PARIKH

Sep 16th, 2005

ans: 1* N + 2*N = 3N ways

pradeep narra

Jan 5th, 2006

If f(n) is the number of ways to climb n steps;

f(1)=1;

f(2)=2;

then f(n)=f(n-1)+f(n-2);

this is nothing but a fibonacci series 1,2,3,5,8,13,21,34, and so on

Ravindra

Jul 6th, 2006

by n ways.

Suppose n=2 then one can go by 2 ways taking 1 step at a time or taking 2 at a time when n=3 then by 3 ways ....... so for n stairs one can go by n ways.

shalini

Sep 24th, 2006

nC1+nC2 ways

i.e.. in [n(n+1)] /2 ways. As the action here is not simultaneous we add both the possibilities.

This can be solved easily by considering an analogy. Cansider two steps as one step...... Then there are totally n/2 steps. Now He has to land on every step(new step-doubled) because he cannot take more than two steps at a time. Now either one or two steps can be selected in a (newer) step in 2C1 +2C2 ways... Total No. of ways to climb is n/2*(2C1+2C2) ways...

Its not the n+1th fibonacci no., the ans is nth fibanacci no.
for eg:-
if no of steps is 3 then n=3
if no of steps is 4 then n=5
if no of steps is 5 then n=8
for 6 n=13
for 7 n=21
for 8 n=34 and so on...

## There is A staircase having n steps (odd or even). A person standing at the base Can take one or two-steps at a time. My query is in how many ways can The stairs can be climbed?

This question is related to Infosys Interview## Related Answered Questions

## Related Open Questions