How to show that $\sum_{x=1}^\infty \prod_{i=1}^{x-1} (1-i/n) \sim \sqrt{\frac{\pi n}{2}}$?

Question

How can one show that asymptotically

$$\sum_{x=1}^\infty \prod_{i=1}^{x-1} \left(1-\frac{i}{n}\right) \sim \sqrt{\frac{\pi n}{2}} \; ?$$

A non rigorous argument is to say that for large $n$, $(1-i/n) \approx e^{-n}$ and then make the approximation $\prod_{i=1}^{x-1} (1-i/n) \approx e^{-x^2/2n}$. Finally we approximate the sum by an integral and use the fact that

$$\int_{x=0}^{\infty} e^{-x^2/2n} = \sqrt{\frac{\pi n}{2}}.$$

Answer 1

The inner product is $\dfrac{(n-1)!}{n^{x-1}(n-x)!}$. The terms beyond $x=n+1$ in the summation are zero. Hence, the summation is $$\sum_{x=1}^n \dfrac{(n-1)!}{n^{x-1}(n-x)!} = \underbrace{\dfrac{(n-1)!}{n^{n-1}} \sum_{t=0}^{n-1} \dfrac{n^t}{t!} \sim \dfrac1{n^{n-1}} \sqrt{2\pi (n-1)} \left(\dfrac{n-1}{e}\right)^{n-1} \dfrac{e^n}{2}}_{\text{Stirling and the fact that $e^x$ has equal mass on either side of $x^x$ in its Taylor series }} \sim \sqrt{\dfrac{\pi n}2}$$

Answer 2

Let's analyze your approximation.

Since $$ \frac{x}{1+x}\le\log(1+x)\le x $$ for all $x\gt-1$, we have $$ \begin{align} \sum_{i=1}^{x-1}\log\left(1-\frac{i}{n}\right) &\le\sum_{i=1}^{x-1}\left(-\frac{i}{n}\right)\\ &=-\frac{x(x-1)}{2n} \end{align} $$ and for $x\le n$, $$ \begin{align} \sum_{i=1}^{x-1}\log\left(1-\frac{i}{n}\right) &\ge\sum_{i=1}^{x-1}\left(-\frac{i}{n-i}\right)\\ &\ge\frac{n}{n-x+1}\sum_{i=1}^{x-1}\left(-\frac{i}{n}\right)\\ &=-\frac{x(x-1)}{2(n-x+1)} \end{align} $$ Therefore, $$ e^{-\large\frac{x(x-1)}{2(n-x+1)}}\le\prod_{i=1}^{x-1}\left(1-\frac{i}{n}\right)\le e^{-\large\frac{x(x-1)}{2n}} $$ The ratio of the bounds is $$ e^{\large\frac{x(x-1)^2}{2n(n-x+1)}} $$ For $n\ge6$ and $x\le n^{3/5}$, the ratio of the bounds is at most $$ e^{\large n^{-1/5}} $$ which can be made as close to $1$ as we wish by making $n$ large. The maximum sum for $x\gt n^{3/5}$ can be estimated by integrals to be at most $$ \frac12n^{2/5}e^{-\large n^{1/5}} $$ which can be made as close to $0$ as we wish by making $n$ large.

The ratio between $e^{-\large\frac{x^2}{2n}}$ and $e^{-\large\frac{x(x-1)}{2n}}$ is $e^{\large\frac{x}{2n}}\le e^{\frac12\large n^{-2/5}}$, for $x\le n^{3/5}$, which is even closer to $1$ than the previous ratio, so we can make that simplification and still be fine in the limit.

Now we can use an integral to approximate the sum $$ \sum_{x=1}^\infty e^{-\large\frac{x^2}{2n}}\sim\int_0^\infty e^{-\large\frac{x^2}{2n}}\,\mathrm{d}x=\sqrt{\frac{n\pi}2} $$