approximate $\sum_{k=0}^n {n \choose k} k! n^{-k} \sim {\sqrt{\pi n}\over \sqrt{2}}$

Question

Show that as $ n \to \infty $

$$\sum_{k=0}^n {n \choose k} k! n^{-k} \sim {\sqrt{\pi n}\over \sqrt{2}}.$$

Answer 1

By the definition of the $\Gamma$ function and the binomial theorem: $$\begin{eqnarray*} \sum_{k=0}^{n}\binom{n}{k}\frac{k!}{n^k} &=& \int_{0}^{+\infty}e^{-x}\sum_{k=0}^{n}\binom{n}{k}\frac{x^k}{n^k}\,dx \\ &=&\int_{0}^{+\infty}\left(1+\frac{x}{n}\right)^n e^{-x}\,dx\end{eqnarray*}$$ and the last integral can be approximated by using Laplace's method.

Since $\left(1+\frac{x}{n}\right)e^{-x/n}\approx e^{-\frac{x^2}{2n^2}}$, for large $n$s we have: $$ \sum_{k=0}^{n}\binom{n}{k}\frac{k!}{n^k} \approx \int_{0}^{+\infty}\exp\left(-\frac{x^2}{2n}\right)\,dx = \sqrt{\frac{\pi n}{2}}$$ as wanted.