I recently came across this recurrence for the coupon collector problem:
$$\text{draws}(n) = \text{draws}(n-1) \cdot\dfrac{n}{n-1} + 1$$
where $\text{draws}(n)$ is the expected number of coupons to be drawn to get all $n$ unique coupons.
Why is this recurrence true? I would prefer an intuitive approach.
On
With "draws(n)" you seem to mean the expected number of draws to get all elements, if $n$ have to be collected.
The probability to get an object that is not already drawn, decreases from $\frac{n}{n}=1$ downto $\frac{1}{n}$. So, the expected number of draws needed is $$E_n=\sum_{j=1}^n \frac{n}{j}=n\cdot H(n)$$
Therefor we have $$E_{n-1}=\sum_{j=1}^{n-1} \frac{n-1}{j}$$
This implies $$\frac{n}{n-1}\cdot E_{n-1}=\sum_{j=1}^{n-1}\frac{n}{j}$$ hence $$E_n=\frac{n}{n-1}\cdot E_{n-1}+ \frac{n}{n}=\frac{n}{n-1}\cdot E_{n-1}+1$$
Ah, I've figured out the idea behind it. The following argument I give is somewhat nonrigorous and I would treat it with suspicion, but it at least conveys the basic idea that you can then take as a starting point for a search for an argument you can be confident in.
To draw $n$ distinct coupons, you must:
The second bullet point is almost the coupon collector problem for $n-1$ kinds of coupons; the difference is that a fraction $\frac{1}{n}$ of your draws "don't count" because they were of the same type as the first coupon.
In other words, on average you have to make $\frac{n}{n-1}$ draws to get one more pick at the $n-1$ coupon subproblem. Thus,
$$ \text{draws}(n) = 1 + \frac{n}{n-1} \text{draws}(n-1) $$