Combinations to Reach Nth Stair by moving up one step or two step at a time.

The answer to this can be found out by induction.

To reach the N^th Stair, we can reach by jumping one step from the (N - 1)^th stair or jumping 2 steps from the (N-2)th ^chair.

If we denote Number of Ways of reach N as F(N)

F(N) = F(N-1) + F(N-2).

Does that ring any bells ?

It is the general form of the Nth term of the Fibonacci sequence.

So to reach the Nth stair, the (N+1)th number in the Fibonacci sequence is the total Number of combination, if the sequence starts from 0 as shown below.
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
etc...