I was recently solving some problems on Linearity of Expectation. I was trying to solve the Coupon collector problem. The problem is: Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once? This is how I tried to solve the problem:

E[Number of coupons needed to draw so that each coupon comes atleast once]

E[Number of coupons drawn till *i*'th coupon is drawn for the first time]

This comes from the Linearity of Expectation (Link) since independency or dependency of events does not matter.

Now, let E[Number of coupons drawn till *i*'th coupon is drawn for the first time] = x

This can be solved by applying the following recursive equation,

*x* = 1 + ((*n* - 1) / *n*) * *x*

On solving, we get x = n.

Thus, E[Number of coupons needed to draw so that each coupon comes atleast once] = *n*^{2}

I know that I am wrong somewhere since the answer is *n* * *H*_{n}, but I don't know where exactly does it go wrong. I have discussed this with my friend kr_abhinav, but we couldn't find the mistake in the proof as well.