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 Nth 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... 25 Jan, 2010
Comments (0)
You may also like
On Facebook
Email Newsletter