Where Fibonacci Numbers Show Up

"How many ways can you climb a staircase of $n$ steps if you take one or two steps at a time?" is one of the most-repeated counting questions in interviews, and it isn't really about staircases — it's the Fibonacci sequence wearing a costume. Recognizing that a counting problem has this shape lets you write down the answer's recurrence in seconds instead of enumerating cases.

Why the same recurrence keeps appearing

The staircase problem has a clean recursive argument: to reach step $n$, your last move was either a single step from step $n-1$, or a double step from step $n-2$. Every valid path falls into exactly one of these two groups, and they don't overlap, so the total count is

$$f(n) = f(n-1) + f(n-2) .$$

In plain English: the number of ways to finish is the number of ways to finish one step early (then take a single step) plus the number of ways to finish two steps early (then take a double step). With $f(1) = 1$ and $f(2) = 2$, this generates $1, 2, 3, 5, 8, 13, \ldots$ — the Fibonacci sequence, just shifted by an index. The exact same argument reappears any time a puzzle asks you to build a sequence out of pieces of size 1 and 2 with no other constraint: tiling a $1\times n$ strip with $1\times1$ and $1\times2$ tiles, or counting binary strings of length $n$ with no two consecutive 1s.

Worked example: tiling a 1×n strip

How many ways can you tile a $1 \times 8$ strip using $1\times1$ squares and $1\times2$ dominoes? Let $T(n)$ be the count for a strip of length $n$. The tile covering the last cell is either a $1\times1$ square (leaving a $1\times(n-1)$ strip to tile) or the right half of a $1\times2$ domino (leaving a $1\times(n-2)$ strip). So $T(n) = T(n-1) + T(n-2)$, with $T(0) = 1$ (empty strip, one way — do nothing) and $T(1) = 1$. Building up: $T(2)=2, T(3)=3, T(4)=5, T(5)=8, T(6)=13, T(7)=21, T(8)=34$. There are 34 ways to tile the strip — and you found it by adding two numbers seven times, not by drawing tilings.

Worked example: no two consecutive 1s

How many binary strings of length 5 have no two consecutive 1s? Let $g(n)$ count valid strings of length $n$. If the string ends in 0, the first $n-1$ characters form any valid string of length $n-1$. If it ends in 1, the character before it must be 0 (to avoid "11"), so the first $n-2$ characters form any valid string of length $n-2$. Hence $g(n) = g(n-1) + g(n-2)$, with $g(1)=2$ (0 or 1) and $g(2)=3$ (00, 01, 10). That gives $g(3)=5, g(4)=8, g(5)=13$ — 13 valid strings of length 5.

What this means in practice

Once you spot a "last piece has two options, and the two resulting sub-problems are disjoint and smaller" structure, you can skip straight to writing $f(n) = f(n-1) + f(n-2)$ and reading off a table, which is both faster and less error-prone than direct enumeration. The same shape underlies simple combinatorial models of order-arrival patterns and coin-flip streaks in quant interviews — anywhere the last unit of "space" can be filled in exactly two mutually exclusive ways.