> [!Problem] > How many ways can a frog hop up a twelve-step staircase if the frog can hop either one or twi steps on each hop? > [!Solution] > Denote $f(n)$ as the number ways that a frog hops to the n-th stair. Clearly $f(1)=1$ and $f(2)=1+1=2$ > For the $n$-th stair, there is only two ways to reach > - hop from the $(n-1)$-th stair > - hop from the $(n-2)$-th stair > $\implies f(n)=f(n-1)+f(n-2)$, with $f(1)=1,f(2)=2$ > > > Note that this describes a [[Fibonacci Sequence]].