Problem: There are 12 steps. I descend one step at a time or two at a time. In how many different ways can I come downstairs?
Solution:
Let f(n) = no of ways in which n steps can be descended.
One step can be descended in only one way - descend that step.
Therefore, f(1) = 1
Two steps can be descended in two ways - one way is to descend one step at a time and another way is to descend both steps at once.
Therefore, f(2) = 2
If you have to descend n steps, then you can choose any of the following two options
1. Descend one step. After that you have to descend n - 1 steps.
2. Descend two steps at once. After that you have to descend n - 2 steps.
Therefore, no. of ways to descend n steps = no. of ways to descend n - 1 steps + no. of ways to descend n - 2 steps.
Or,
f(n) = f(n - 1) + f(n-2)
If we write the sequence of the values of f(n), then we get a sequence in which first term = 1 because f(1) = 1, second term = 2 because f(2) = 2 and after that each term is the sum of previous 2 terms. (Note: In case you are interested, it is Fibonacci sequence .)
There are 12 steps. Therefore, write the sequence for 12 terms.
f(1) = 1
f(2) = 2
f(3) = f(1) + f(2) = 1+2 = 3
f(4) = f(2)+f(3) = 2+3 = 5
f(5) = f(3)+f(4) = 3+5 = 8
f(6) = f(4) + f(5) = 5+8 = 13
f(7) = f(5) + f(6) = 8+13 = 21
f(8) = f(6) + f(7) = 13 + 21 = 34
f(9) = f(7) + f(8) = 21+34 = 55
f(10) = f(8) + f(9) = 34+55 = 89
f(11) = f(9) + f(10) = 55+89 = 144
f(12) = f(10) + f(11) = 89 + 144 = 233
No. of ways to descend 12 steps = f(12) = 233
Ans: 233