Let c(i-1) = the total for a staircase with i-1 steps. Now add one step to the beginning. You have two choices: start with one step and then do c(i-1), or start with two steps and then do c(i-2). In other words, c(i) = c(i-1) + c(i-2). The basis for the recurrence is c(0) = c(1) = 1.

This is exactly the Fibonacci sequence. I submit that the solution to this problem of n steps is Fib(n+1). Let's verify for small values of n:

1 steps: There's only one way to take one step. (1)

2 steps: There are 2 ways (1+1) or (2)

3 steps: 3 ways (1+1+1), (1+2), (2+1)

4 steps: 5 ways (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2)

2.*1*n distinct ways to climb