Suppose we want to climb to the nth step, and .
There are 2 possible ways of getting there:
- We are at the n-1 step, and we jump to the next. ways of doing this, since we have to get to the n-1 step
- We are at the n-2 step, and we jump directly to n. ways of doing this
So we have
Now (there's one way of doing nothing) and and our sequence is determined