## Staircase climbing

Question:

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 ?

Thus, the number of possibilities for $n$ stairs will be the number of possibilities to climb $n-1$ stairs (in case the last step is one stair long) plus the number of possibilities to climb  $n-2$ stairs (in case the last step is two stairs long).
$S(n)=S(n-1)+S(n-2)$ with $S(1)=1$ and $S(2)=2$