Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is a staircase and some person say X can take 1 step or 2 steps . So how many ways can he take in total to climb up the staircase where there are n steps in total. Also what will be the minimum steps for him to climb up the staircase ? I think the number of minimum steps would be $\frac{n}{2}$ if $n$ is even and $\frac{n}{2}$ +$1$ if $n$ is odd but not sure about the total number of ways .

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

Total number of ways to climb the staircase is given recursively as:

T(n) = T(n-1) + T(n-2) for n >= 3.

T(1) = 1

T(2) = 2

The minimum number of steps to climb is n/2 if n is even else [n/2] + 1 where [x] denotes greatest integer less than or equal to x.

share|improve this answer
    
I do not want the recursion . I want the solution to the recursion . –  Geek Sep 4 '12 at 11:03
    
Clearly these are the Fibonacci numbers...it is the same recursion and roughly the same starting values. –  fretty Sep 4 '12 at 11:05
    
@fretty For Fibonacci sequence we have $F_0$ =0 and $F_1$ = 1 . The base cases are not the same . –  Geek Sep 4 '12 at 11:13
    
This is the same recursions as the one for Fibonacci numbers. The closed form solution is T(n) = [{(1 + sqrt 5)/2}^n + {(1 - sqrt 5)/2}^n]/sqrt 5 –  ajay Sep 4 '12 at 11:15
1  
Yes but it is exactly the same sequence just shifted one to the right! Start with $F_1$ and $F_2$ as base cases...so $T(n) = F_n$. –  fretty Sep 4 '12 at 11:32
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.