How to calculate $\sum \limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right)$

Question

What are the asymptotics of the following sum as $n$ goes to infinity? $$ S =\sum\limits_{x=0}^{n} \frac{n!}{(n-x)!\,n^x}\left(1-\frac{x(x-1)}{n(n-1)}\right) $$

The sum comes from Probability of finding a duplicate or two numbers. Consider a random process where integers are sampled uniformly with replacement from $\{1...n\}$. Let $X$ be a random variable that represents the number of samples until either a duplicate is found or both the values $1$ and $2$ have been found. So if the samples where $1,6,3,5,1$ then $X=5$ and if it was $1,6,3,2$ then $X=4$. This sum is therefore $\mathbb{E}(X)$.

We therefore know that $S = \mathbb{E}(X) \leq \text{mean time to find a duplicate} \sim \sqrt{\frac{\pi}{2} n}$.

Taking the first part of the sum, $$\sum_{x=0}^{n} \frac{n!}{(n-x)!\,n^x} = \left(\frac{e}{n} \right)^n \Gamma(n+1,n) \sim \left(\frac{e}{n} \right)^n \frac{n!}{2} \sim \sqrt{\frac{\pi}{2} n}. $$

Answer 1

Let $N_n$ denote a Poisson random variable with parameter $n$, then $$ S_n=\frac{n-2}{n-1}n!\left(\frac{\mathrm e}n\right)^n\mathbb P(N_n\leqslant n)+\frac2{n-1}. $$ As a consequence, $\lim\limits_{n\to\infty}S_n/\sqrt{n}=\sqrt{\pi/2}$.

To show this (for a shorter proof, see the end of this post), first rewrite each parenthesis in $S_n$ as $$ 1-\frac{x(x-1)}{n(n-1)}=\frac2n(n-x)-\frac1{n(n-1)}(n-x)(n-x-1). $$ Thus, $\displaystyle S_n=n!\,(2U_n-V_n)$ with $$ U_n=\frac1n\sum_{x=0}^n\frac1{n^x}\frac{n-x}{(n-x)!}=\sum_{y=1}^n\frac1{n^y}\frac1{(n-y)!}=n^{-n}\sum_{x=0}^{n-1}\frac{n^x}{x!}, $$ and $$ V_n=\frac1{n(n-1)}\sum_{x=0}^n\frac1{n^x}\frac{(n-x)(n-x-1)}{(n-x)!}=\frac{n}{n-1}\sum_{z=2}^n\frac1{n^z}\frac1{(n-z)!}, $$ that is, $$ V_n=\frac{n}{n-1}n^{-n}\sum_{x=0}^{n-2}\frac{n^x}{x!}. $$ Introducing $$ W_n=n^{-n}\sum_{x=0}^n\frac{n^x}{x!}, $$ this can be rewritten as $$ U_n=W_n-\frac1{n!},\qquad V_n=\frac{n}{n-1}\,\left(W_n-\frac2{n!}\right), $$ hence $$ S_n=n!\left(2\left(W_n-\frac1{n!}\right)-\frac{n}{n-1}\left(W_n-\frac2{n!}\right)\right)=n!\frac{n-2}{n-1}W_n+\frac2{n-1}. $$ The proof is complete since $$ W_n=n^{-n}\mathrm e^n\cdot\mathrm e^{-n}\sum_{x=0}^n\frac{n^x}{x!}=n^{-n}\mathrm e^n\cdot\mathbb P(N_n\leqslant n). $$ Edit: Using the distribution of $N_n$ and the change of variable $x\to n-x$, one gets directly $$ S_n=n!\left(\frac{\mathrm e}n\right)^n\left(\mathbb P(N_n\leqslant n)-\mathbb E(u_n(N_n))\right), $$ with $$ u_n(t)=\frac{(n-t)(n-t-1)}{n(n-1)}\,\mathbf 1_{t\leqslant n}. $$ Since $N_n/n\to1$ almost surely when $n\to\infty$, $u_n(N_n)\to0$ almost surely. Since $u_n\leqslant1$ uniformly, $\mathbb E(u_n(N_n))\to0$. On the other hand, by the central limit theorem, $\mathbb P(N_n\leqslant n)\to\frac12$, hence Stirling's equivalent applied to the prefactor of $S_n$ yields the equivalent of $S_n$.

Edit-edit: By Berry-Esseen theorem, $\mathbb P(N_n\leqslant n)=\frac12+O(\frac1{\sqrt{n}})$. By the central limit theorem, $\mathbb E(u_n(N_n))=O(\frac1n)$. By Stirling's approximation, $n!\left(\frac{\mathrm e}n\right)^n=\sqrt{2\pi n}+O(\frac1{\sqrt{n}})$. Hence, $S_n=\sqrt{\pi n/2}+T_n+o(1)$ where $\limsup\limits_{n\to\infty}|T_n|\leqslant 2C\sqrt{2\pi}(1+\mathrm e^{-1})$ for any constant $C$ making Berry-Esseen upper bound true, hence $\limsup\limits_{n\to\infty}|T_n|\lt3.3$.

Answer 2

The result below is not completely rigorous though I believe the argument (and especially the result) to be essential correct.

Defining $$f_n(k) = \frac{n!}{(n-k)!\,n^k}\left[1-\frac{k(k-1)}{n(n-1)}\right],$$ we transform the sum $$S_n=\sum_{k=0}^n f_n(k) =\sum_{k=1}^{n} k [f_n(k-1) -f_n(k)] $$ using summation by parts. Some straightforward calculation shows $$g_n(k) = f_n(k-1)- f_n(k) = \frac{(k-1)(k+n)}{n(n-1)} \frac{n!}{ n^k (n-k)!}.$$ Because of the definition of $f_n(k) = P(X\ge x)$, we know that $g_n(k) \geq 0$ for $k\in[1,n]$.

We have that $$\frac{n!}{(n-k)!} \frac{1}{n^k} = \frac{n}{n} \frac{n-1}{n} \cdots \frac{n-k+1}{n} = \prod_{j=1}^{k-1} \left(1- \frac{j}{n}\right)$$ thus ($k\ll n$) $$\log \left[\frac{n!}{(n-k)!} \frac{1}{n^k}\right] = \log\left[ 1 -\sum_{j=1}^{k-1}\frac{j}{n} + \mathcal{O}\left(\frac{1}{n^2}\right)\right] = - \frac{k(k-1)}{2n} + \mathcal{O}\left(n^{-2}\right).$$ You can see that for large $n$ this function is maximal for $k=1$ with a broad peak of size $\simeq \sqrt{n}$. Nevertheless, because for large $n$, $\sqrt{n} \ll n$ the most weight of the sum is concentrated for small $k \lesssim \sqrt{n} \ll n$.

We can simplify $$S_n =\sum_{k=1}^n k g_n(k) \sim \sum_{k=1}^n \frac{k (k-1)\overbrace{(k+n)}^{\approx n}}{\underbrace{n(n-1)}_{\approx n^2}} e^{-k(k-1)/2n} \sim -2 \partial_{\alpha}\sum_{k=1}^n e^{-\alpha k(k-1)/2n}\bigg|_{\alpha=1}.$$

Because the summand changes little from $k$ to $k+1$, the remaining sum can be approximated by the integral $$ \sum_{k=1}^n e^{-\alpha k(k-1)/2n} \sim \int_0^n e^{-\alpha x^2/2n} \sim \int_0^\infty e^{-\alpha x^2/2n} = \sqrt{\frac{\pi n}{2 \alpha}}.$$

Concluding, we have $$S_n \sim -2 \partial_{\alpha} \sqrt{\frac{\pi n}{2 \alpha}}\,\bigg|_{\alpha=1}= \sqrt{\frac{\pi n}{2}}.$$

Edit: let us think about the errors made in each step:

1) in the expansion of $$ \log \left[\frac{n!}{(n-k)!} \frac{1}{n^k}\right]$$ the next term is $\mathcal{O}(k^3/n^2) = \mathcal{O}(n^{-1/2})$ using the fact that $k\leq \sqrt{n}$.

2) We have $k+n = n [1+ \mathcal{O}(n^{-1/2})]$ and $n(n-1) = n^2[1+\mathcal{O}(n^{-1})]$.

3) The error in replacing the sum with the integral $$ \sum_{k=1}^n e^{-\alpha k(k-1)/2n} \sim \int_1^{n-1} e^{-\alpha x(x-1)/2n} $$ is given by the maximum of $\partial_x e^{- x(x-1)/2n}$ times $\sqrt{n}$, i.e., the error is of the order $n^{-1/2}$.

4) Replacing $x(x-1)$ with $x^2$ introduces a relative error of $n^{-1/2}$.

5) Extending the upper bound of the integral to infinity contributes with an error $\propto e^{-n}$.

s) Summarizing, we expect $S_n = \sqrt{\pi n/2} + \mathcal{O}(1)$.

Answer 3

I get $$S = \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + O(n^{-1/2+4\epsilon}).$$

---

An asymptotic for the summand.

If $x \leq n^{1/2+\epsilon}$, then Stirling's approximation yields $$\log\left(\frac{n!}{(n-x)!n^x}\right) = - \frac{x^2}{2n} + \frac{x}{2n} - \frac{x^3}{6n^2} + O(n^{-1+4\epsilon}) \tag{1}.$$ To obtain this, we need to rewrite $\log(n-x)$ as $\log(n) \log(1-x/n)$, use the Maclaurin series $\log(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} + O(x^4)$ to get the dominant terms of $\log(1-x/n)$, and then crunch through a lot of algebra. Most of the initially dominant terms cancel.

Thus, if $x \leq n^{1/2+\epsilon}$, $$\frac{n!}{(n-x)!n^x} = e^{-x^2/2n} \left(1 + \frac{x}{2n} - \frac{x^3}{6n^2} + O(n^{-1+4\epsilon})\right),$$ where we use the Maclaurin series $e^x = 1 + x + O(x^2)$ on all but the dominant term in Eq. (1).

Bounding the tail sum.

Since $\displaystyle \frac{n!}{(n-x)!n^x}$ is a decreasing function of $x$, if $x > n^{1/2+\epsilon}$, then $\displaystyle \frac{n!}{(n-x)!n^x} = O(e^{-x^2/2n}) = O(e^{-n^{2\epsilon}/2})$. Thus for the tail sum we get $$\sum_{x > n^{1/2} + \epsilon} \frac{n!}{(n-x)!n^x} = O(ne^{-n^{2\epsilon}/2}),$$ which is exponentially small. Therefore we can ignore it from here out for asymptotic purposes.

A useful asymptotic sum.

Problem 9.30 (p. 491) in Concrete Mathematics states that $$\sum_{k \geq 0} k^r e^{-r^2/n} = \frac{1}{2} n^{(r+1)/2} \Gamma\left(\frac{r+1}{2}\right) - \frac{B_{r+1}}{(r+1)!} + O(n^{-1}) \tag{2},$$ where $B_r$ is the $r$th Bernoulli number. (An outline of the proof is given in the answer section of the book.)

The asymptotic for the first, dominant term.

Equation (2) gives us \begin{align*} \sum_{x =0}^n \frac{n!}{(n-x)!n^x} = &\frac{1}{2} \sqrt{2n} \Gamma(1/2) + \frac{1}{2} + O(n^{-1}) + \frac{1}{2n}\left(\frac{1}{2} 2n \Gamma(1) + O(1)\right) \\ &- \frac{1}{6n^2} \left(\frac{1}{2} (2n)^2 \Gamma(2) + O(1)\right) + O(n^{-1/2 + 4 \epsilon}) \\ = & \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + O(n^{-1/2 + 4 \epsilon}). \end{align*}

An asymptotic for the second term.

For the second term $\displaystyle \sum_{x =0}^n \frac{n!}{(n-x)!n^x} \frac{x(x-1)}{n(n-1)},$ a similar analysis holds. We can ignore the tail sum when $x > n^{1/2+\epsilon}$ because it is even smaller than the tail sum in the first term. If $x \leq n^{1/2+\epsilon}$, we get $$\frac{n!}{(n-x)!n^x} \frac{x(x-1)}{n(n-1)} = e^{-x^2/2n} O(n^{-1+\epsilon}).$$ Therefore, by Equation (2), $$\sum_{x=0}^n \frac{n!}{(n-x)!n^x} \frac{x(x-1)}{n(n-1)} = O(n^{-1/2+\epsilon}).$$

Finally.

All together, then,

$$S = \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + O(n^{-1/2+4\epsilon}).$$

---

Additional comments.

Incidentally, the sum $\displaystyle \sum_{x=0}^n \frac{n!}{(n-x)!n^x}$ is one that appears in several places in Knuth's work, and in The Art of Computer Programming, Vol. I, p. 120, he gives the asymptotic (in his notation) $$\sum_{x=0}^n \frac{n!}{(n-x)!n^x} = 1 + Q(n) = \sqrt{\frac{\pi n}{2}} + \frac{2}{3} + \frac{1}{12}\sqrt{\frac{\pi}{2n}} - \frac{4}{135n} + \frac{1}{288} \sqrt{\frac{\pi}{2n^3}} + O(n^{-2}).$$