# Total number of ways and minimum number of steps of going up the stair case?

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.

• 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
• 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