Coupon Collector Problem - expected number of draws for some coupon to be drawn twice

Suppose that there are $n$ different coupons, equally likely, from which coupons are being randomly drawn with replacement. Find the expected number of draws for some coupon to be drawn twice.

I've attempted to solve this from the basic definition of expectation. If $N$ is a randomly variable for the number of draws for some coupon to be drawn twice, then $1\lt N\le n+1$ and

$$E[N]=\sum_{i=2}^{n+1} n*Pr(N=n)\\ =2*\left(\frac{1}{n}\right)+3*\left(\frac{n-1}{n}\right)\left(\frac{2}{n}\right)+4*\left(\frac{n-1}{n}\right)\left(\frac{n-2}{n}\right)\left(\frac{3}{n}\right)+...$$

(Sorry for not finishing the equation, hopefully you get the idea, it goes up to $n+1$, my latex maths is pretty crap.)

Is this correct? How do I evaluate this sum or is there a closed-form solution to this sum? Is there a better way to solve this?

• The material in the referred to question is relevant but quite different. For one thing, it is concerned with the expected number of draws in order to get two pairs of duplicates, not $1$. – André Nicolas Jun 3 '13 at 18:51
• Wikipedia gives an expression for the mean number needed in the birthday problem. It is not in a closed form. – Henry Jun 24 '13 at 23:08
• You never use the index $i$. I'm guessing some of those $n$s should be $i$s. – dfeuer Jun 25 '13 at 4:00

\begin{align} E[N]&=\sum_{k=0}^n\textsf{Pr}(N\gt k)\\ &=\sum_{k=0}^n\frac{n!}{(n-k)!n^k}\\ &=\sum_{k=0}^n\frac{n!}{k!n^{n-k}}\\ &=\frac{n!}{n^n}\sum_{k=0}^n\frac{n^k}{k!}\\ &\sim\frac{n!}{n^n}\frac{\mathrm e^n}2\\ &\sim\sqrt{\frac{\pi n}2}\;, \end{align}

where the first approximation takes the terms of the exponential series to be approximately symmetric about its maximum at $k=n$, and the second approximation is Stirling's. According to Wikipedia, the next term in the expansion in terms of $\sqrt n$ is $-\frac13$.

• Though you also need to add $1$ – Henry Nov 16 '16 at 21:56
• @Henry: True, thanks. So the next term in the expansion is actually $+\frac23$. – joriki May 30 '18 at 23:21