**Given n stairs, how many number of ways can you climb if u use either 1, 2 or 3 at a time?**

When you find any difficult problem first step is to reduce it to very small problem with example

Consider 3 steps. you can take only one at a time. Then number of ways are 1: ie {(1,1,1)}

Consider 2 steps. you can take 1 or 2 at a time. Then number of ways are 2: ie {(1,1), (2)}

Consider 3 steps. you can take 1 or 2 at a time Number of ways : 3 ie : {(1,2),(2,1),(1,1,1)}

Consider 4 steps. you can take 1 or 2 at a time Number of ways : 5

ie {(1,1,1,1), (1,2,1),(1,1,2),(2,1,1),(2,2)}

Consider 4 steps. you can take 1 or 2 at a time Number of ways : 5

ie {(1,1,1,1), (1,2,1),(1,1,2),(2,1,1),(2,2)}

See carefully 2,3,5……

This makes Fibonacci series

because If we are at Nth step then to reach at bottom (same as climbing) at each step we can decide whether to take N-1 or N-2 step and at each decision further option keeps open.

so Function if we can take 1 or 2 is

F(n) = F(n-1) + F(n-2) ;

Similarly if we can take three steps 1,2 or 3

F(n) = F(n-1) + F(n-2) + F(n-3) ;