Lesson 4

Again, it can be observed that all ways to climb \(n\) steps naturally divide into two classes: those starting with a single step and those starting with a jump. Clearly, the first class contains \(S(n-1)\) ways, and the second contains \(S(n-2)\) ways. Taking into account the initial conditions \(S(0)=1\) (there is one way to climb zero steps—do nothing) and \(S(1)=1\), we obtain \(S(n)=F(n+1)\).