You are climbing a stair case. Each time you can either climb 1 stair or 2 stairs. The staircase has n stairs. In how many distinct ways can you climb the staircase ?
There are two possibilities for the last performed step: one stair or two stairs.
Thus, the number of possibilities for stairs will be the number of possibilities to climb stairs (in case the last step is one stair long) plus the number of possibilities to climb stairs (in case the last step is two stairs long).
Looks like the answer is related to Fibonacci numbers: