1
$\begingroup$

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 .

1 Answers 1

2

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.

  • 0
    I do not want the recursion . I want the solution to the recursion .2012-09-04
  • 0
    Clearly these are the Fibonacci numbers...it is the same recursion and roughly the same starting values.2012-09-04
  • 0
    @fretty For Fibonacci sequence we have $F_0$ =0 and $F_1$ = 1 . The base cases are not the same .2012-09-04
  • 0
    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 52012-09-04
  • 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$.2012-09-04
  • 0
    @fretty: you mean $T(n)=F_{n+1}$. Remember $F_0=0$, $F_1=1$, $F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$ (ha! finally caught up), $F_6=8$, ...2012-09-04
  • 0
    And the minimum number of steps (not ways!) can be written as $\lfloor(n+1)/2\rfloor$ for all $n\geq0$.2012-09-04
  • 0
    Oh yeah silly me!2012-09-05