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 .


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.

  • $\begingroup$ I do not want the recursion . I want the solution to the recursion . $\endgroup$ – Geek Sep 4 '12 at 11:03
  • $\begingroup$ Clearly these are the Fibonacci numbers...it is the same recursion and roughly the same starting values. $\endgroup$ – fretty Sep 4 '12 at 11:05
  • $\begingroup$ @fretty For Fibonacci sequence we have $F_0$ =0 and $F_1$ = 1 . The base cases are not the same . $\endgroup$ – Geek Sep 4 '12 at 11:13
  • $\begingroup$ 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 $\endgroup$ – ajay Sep 4 '12 at 11:15
  • 1
    $\begingroup$ 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$. $\endgroup$ – fretty Sep 4 '12 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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