Hopping Rabbit: Counting Ways Up an n-Step Staircase
A rabbit sits at the bottom of a staircase with $n$ steps. On every hop it climbs either exactly 1 step or exactly 2 steps, and it must land exactly on the top step (it cannot overshoot). Two routes are different if their sequences of hop sizes differ, so for $n = 3$ the routes $1\text{-}2$, $2\text{-}1$ and $1\text{-}1\text{-}1$ are three different routes.
Let $f(n)$ be the number of distinct routes to the top.
(a) Find a recurrence for $f(n)$, with its initial conditions, and identify the resulting sequence.
(b) Evaluate $f(10)$.
Hints
- Condition on the very last hop: it was either a 1-step hop or a 2-step hop. Where was the rabbit just before it?
- Every route to step $n$ is either a route to step $n-1$ followed by a 1-hop, or a route to step $n-2$ followed by a 2-hop, and no route is counted twice.
- $f(n) = f(n-1) + f(n-2)$ with $f(1) = 1$, $f(2) = 2$: the Fibonacci numbers shifted by one index, $f(n) = F_{n+1}$.
Worked Solution
How to Think About It: Do not try to count routes directly by how many 2-hops they contain (that works, but it is a sum of binomial coefficients). Instead think recursively: the last hop of any route lands on step $n$ from either step $n-1$ or step $n-2$. That gives a recurrence immediately.
Quick Estimate: Fibonacci numbers grow like $\varphi^n/\sqrt{5}$ with $\varphi \approx 1.618$, so $f(n) = F_{n+1} \approx 1.618^{n+1}/2.236$. For $n = 10$: $1.618^{11} \approx 199$, divided by $2.236$ gives about $89$.
Formal Solution:
Part (a): Recurrence
*Step 1 -- Partition by the last hop.* Let $A_n$ be the set of routes ending on step $n$ with a 1-hop, and $B_n$ the set ending with a 2-hop. Removing the last hop gives a bijection $A_n \leftrightarrow \{\text{routes to } n-1\}$ and $B_n \leftrightarrow \{\text{routes to } n-2\}$. The two sets are disjoint, so
$$f(n) = f(n-1) + f(n-2), \qquad n \ge 3.$$
*Step 2 -- Initial conditions.* $f(1) = 1$ (a single 1-hop) and $f(2) = 2$ (either $1\text{-}1$ or $2$). Equivalently set $f(0) = 1$ (the empty route) so the recurrence holds from $n = 2$.
*Step 3 -- Identify the sequence.* With $F_1 = F_2 = 1$ the Fibonacci numbers satisfy the same recurrence, and $f(1) = F_2$, $f(2) = F_3$, so by induction
$$f(n) = F_{n+1} = \frac{\varphi^{n+1} - \psi^{n+1}}{\sqrt{5}}, \qquad \varphi = \frac{1+\sqrt{5}}{2},\ \psi = \frac{1-\sqrt{5}}{2}.$$
*Alternative count.* A route with $k$ two-hops and $n - 2k$ one-hops is an arrangement of $n - k$ hops, so $f(n) = \sum_{k=0}^{\lfloor n/2 \rfloor} \binom{n-k}{k}$, the classic diagonal-sum identity for Fibonacci numbers.
Part (b): $f(10)$
Iterating: $1, 2, 3, 5, 8, 13, 21, 34, 55, 89$. So $f(10) = 89$.
Answer: (a) $f(n) = f(n-1) + f(n-2)$ with $f(1) = 1$, $f(2) = 2$, so $f(n) = F_{n+1}$ (Fibonacci). (b) $f(10) = 89$.
Intuition
The count obeys the Fibonacci recurrence because the last move is the only thing that matters: routes to step $n$ split cleanly into "came from $n-1$" and "came from $n-2$." This is the simplest possible dynamic program, and it is the template for a huge family of interview problems (tilings, coin-change counts, lattice paths with restricted steps). In quant work the same decomposition-by-last-step idea drives recursive pricing on binomial trees and path counting for discrete random walks.