Every time you buy a pizza from Pizza Hut, they give you a coupon selected at random from a set of different coupons. How many pizzas do you need to buy on average in order to collect all possible coupons? We know from kindergarten that the answer is . Here’s an intuitive explanation why.

First, let’s look at a cool trick.

Suppose a biased coin with probability of showing heads to be is being tossed repeatedly. How many times, on average, does it need to be tossed to get a heads for the first time? I promise this is related, and the relation will be clear soon.

Anyway, this is a standard geometric distribution and thus we can plug things into known formulas and get the value for our answer. Intuitively, it does look like that should be the answer, since if we rolled a die with faces repeatedly, we would expect to see face #1 after an average of rolls. We can also derive the formula ourselves by writing down an infinite series and using standard summation tricks. But here’s a nice trick that can be used to get to the result immediately.

Let be the expected number of tosses need. Then if the first toss shows a heads, we know that is 1, and if the first toss shows a tails, we know that is . Writing this “in math” we get , which solves to .

Anyway, back to coupon collection. Suppose we already have coupons. What’s the probability that if we buy a pizza, we get a coupon that we do not already have? Clearly, . Thus the expected number of pizzas needed to get one new coupon, from the previous calculations, is . This means the expected number of pizzas required to collect all coupons can just be written as a the sum , which solves to after using the well-known approximation for the Harmonic number.