Fibonacci: Rabbit
A rabbit sits at the bottom of a staircase with \(n\) stairs. The rabbit can hop up only one or two stairs at a time. How many different ways are there for the rabbit to ascend to the top of the stairs?
Answer
Let \(f(n)\) be the number of ways the rabbit can ascend \(n\) stairs. We analyze small cases first:
\[
f(1) = 1 \quad (\text{just one 1-step hop}).
\]
\[
f(2) = 2 \quad (\text{either two 1-step hops, or one 2-step hop}).
\]
For \(n > 2\), the last hop is either:
- A 1-step hop (coming from stair \(n-1\)), or
- A 2-step hop (coming from stair \(n-2\)).
Hence, the recursion:
\[
f(n) = f(n-1) + f(n-2).
\]
This is precisely the Fibonacci sequence.
Thus, the number of different ways for the rabbit to ascend \(n\) stairs is given by \(f(n)\), where
\[
f(n) =
\begin{cases}
1, & n=1, \\
2, & n=2, \\
f(n-1) + f(n-2), & n>2.
\end{cases}
\]