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 and minimum number of steps of going up the stair case?
1
$\begingroup$
combinatorics
1 Answers
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.
-
0I do not want the recursion . I want the solution to the recursion . – 2012-09-04
-
0Clearly 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
-
0This 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 – 2012-09-04
-
1Yes 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
-
0And the minimum number of steps (not ways!) can be written as $\lfloor(n+1)/2\rfloor$ for all $n\geq0$. – 2012-09-04
-
0Oh yeah silly me! – 2012-09-05