The Harmonic Series in Puzzles

The harmonic series is $H_n = 1 + \tfrac{1}{2} + \tfrac{1}{3} + \cdots + \tfrac{1}{n}$. Its terms shrink toward zero, so it's tempting to guess the sum settles down to some finite number — it doesn't. Grouping terms in doubling blocks, $\left(\tfrac{1}{3}+\tfrac{1}{4}\right) > \tfrac{1}{4}+\tfrac{1}{4} = \tfrac{1}{2}$, and the next block of four terms similarly exceeds $\tfrac{1}{2}$, and so on forever — infinitely many blocks each contributing at least $\tfrac{1}{2}$ means the sum grows without bound, just extremely slowly (it takes roughly $e^{100}$ terms to exceed 100).

That slow divergence, $H_n \approx \ln n + 0.5772$, is exactly what makes the coupon collector's problem work: if there are $n$ distinct coupon types and you draw one at random each time, the expected number of draws to collect all $n$ is $n \cdot H_n \approx n \ln n$. Each new coupon gets harder to find in exact proportion to how many you're still missing, and summing those expected waiting times across all $n$ stages produces a harmonic sum.

The same structure appears in the "worm on a rubber band" puzzle (a worm crawls 1cm per day along a band stretched uniformly by 1m per day; whether it ever reaches the end depends on the harmonic series diverging) and in expected-comparisons arguments for algorithms like quicksort.