# Evaluating $\lim\limits_{n\to\infty} e^{-n} \sum\limits_{k=0}^{n} \frac{n^k}{k!}$

I’m supposed to calculate:

$$\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$$

By using W|A, i may guess that the limit is $\frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.

#### Solutions Collecting From Web of "Evaluating $\lim\limits_{n\to\infty} e^{-n} \sum\limits_{k=0}^{n} \frac{n^k}{k!}$"

Edited. I justified the application of the dominated convergence theorem.

By a simple calculation,

\begin{align*} e^{-n}\sum_{k=0}^{n} \frac{n^k}{k!} &= \frac{e^{-n}}{n!} \sum_{k=0}^{n}\binom{n}{k} n^k (n-k)! \\ (1) \cdots \quad &= \frac{e^{-n}}{n!} \sum_{k=0}^{n}\binom{n}{k} n^k \int_{0}^{\infty} t^{n-k}e^{-t} \, dt\\ &= \frac{e^{-n}}{n!} \int_{0}^{\infty} (n+t)^{n}e^{-t} \, dt \\ (2) \cdots \quad &= \frac{1}{n!} \int_{n}^{\infty} t^{n}e^{-t} \, dt \\ &= 1 – \frac{1}{n!} \int_{0}^{n} t^{n}e^{-t} \, dt \\ (3) \cdots \quad &= 1 – \frac{\sqrt{n} (n/e)^n}{n!} \int_{0}^{\sqrt{n}} \left(1 – \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \, du. \end{align*}

We remark that

1. In $\text{(1)}$, we utilized the famous formula $n! = \int_{0}^{\infty} t^n e^{-t} \, dt$.
2. In $\text{(2)}$, the substitution $t + n \mapsto t$ is used.
3. In $\text{(3)}$, the substitution $t = n – \sqrt{n}u$ is used.

Then in view of the Stirling’s formula, it suffices to show that

$$\int_{0}^{\sqrt{n}} \left(1 – \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \, du \xrightarrow{n\to\infty} \sqrt{\frac{\pi}{2}}.$$

The idea is to introduce the function

$$g_n (u) = \left(1 – \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \mathbf{1}_{(0, \sqrt{n})}(u)$$

and apply pointwise limit to the integrand as $n \to \infty$. This is justified once we find a dominating function for the sequence $(g_n)$. But notice that if $0 < u < \sqrt{n}$, then

$$\log g_n (u) = n \log \left(1 – \frac{u}{\sqrt{n}} \right) + \sqrt{n} u = -\frac{u^2}{2} – \frac{u^3}{3\sqrt{n}} – \frac{u^4}{4n} – \cdots \leq -\frac{u^2}{2}.$$

From this we have $g_n (u) \leq e^{-u^2 /2}$ for all $n$ and $g_n (u) \to e^{-u^2 / 2}$ as $n \to \infty$. Therefore by dominated convergence theorem and Gaussian integral,

$$\int_{0}^{\sqrt{n}} \left(1 – \frac{u}{\sqrt{n}} \right)^{n}e^{\sqrt{n}u} \, du = \int_{0}^{\infty} g_n (u) \, du \xrightarrow{n\to\infty} \int_{0}^{\infty} e^{-u^2/2} \, du = \sqrt{\frac{\pi}{2}}.$$

The probabilistic way:

This is $P[N_n\leqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+\cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.

By the central limit theorem, $Y_n=\frac1{\sqrt{n}}(X_1+\cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_n\leqslant 0]\to P[Z\leqslant0]$.

Finally, $P[Z\leqslant0]=\frac12$ and $[N_n\leqslant n]=[Y_n\leqslant 0]$ hence $P[N_n\leqslant n]\to\frac12$, QED.

The analytical way, completing your try:

Hence, I know that what I need to do is to find $\lim\limits_{n\to\infty}I_n$, where
$$I_n=\frac{e^{-n}}{n!}\int_{0}^n (n-t)^ne^tdt.$$

To begin with, let $u(t)=(1-t)e^t$, then $I_n=\dfrac{e^{-n}n^n}{n!}nJ_n$ with
$$J_n=\int_{0}^1 u(t)^n\mathrm dt.$$
Now, $u(t)\leqslant\mathrm e^{-t^2/2}$ hence
$$J_n\leqslant\int_0^1\mathrm e^{-nt^2/2}\mathrm dt\leqslant\int_0^\infty\mathrm e^{-nt^2/2}\mathrm dt=\sqrt{\frac{\pi}{2n}}.$$
Likewise, the function $t\mapsto u(t)\mathrm e^{t^2/2}$ is decreasing on $t\geqslant0$ hence $u(t)\geqslant c_n\mathrm e^{-t^2/2}$ on $t\leqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})\mathrm e^{-1/(2\sqrt{n})}$, hence
$$J_n\geqslant c_n\int_0^{1/n^{1/4}}\mathrm e^{-nt^2/2}\mathrm dt=\frac{c_n}{\sqrt{n}}\int_0^{n^{1/4}}\mathrm e^{-t^2/2}\mathrm dt=\frac{c_n}{\sqrt{n}}\sqrt{\frac{\pi}{2}}(1+o(1)).$$
Since $c_n\to1$, all this proves that $\sqrt{n}J_n\to\sqrt{\frac\pi2}$. Stirling formula shows that the prefactor $\frac{e^{-n}n^n}{n!}$ is equivalent to $\frac1{\sqrt{2\pi n}}$. Regrouping everything, one sees that $I_n\sim\frac1{\sqrt{2\pi n}}n\sqrt{\frac\pi{2n}}=\frac12$.

Moral:
The probabilistic way is shorter, easier, more illuminating, and more fun.

Caveat:
My advice in these matters is, clearly, horribly biased.

Integration by parts yields
$$\frac{1}{k!}\int_x^\infty e^{-t}\,t^k\,\mathrm{d}t=\frac{1}{k!}x^ke^{-x}+\frac{1}{(k-1)!}\int_x^\infty e^{-t}\,t^{k-1}\,\mathrm{d}t\tag{1}$$
Iterating $(1)$ gives
$$\frac{1}{n!}\int_x^\infty e^{-t}\,t^n\,\mathrm{d}t=e^{-x}\sum_{k=0}^n\frac{x^k}{k!}\tag{2}$$
Thus, we get
$$e^{-n}\sum_{k=0}^n\frac{n^k}{k!}=\frac{1}{n!}\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t\tag{3}$$
Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing.
\begin{align} \int_n^\infty e^{-t}\,t^n\,\mathrm{d}t &=n^{n+1}e^{-n}\int_0^\infty e^{-ns}\,(s+1)^n\,\mathrm{d}s\\ &=n^{n+1}e^{-n}\int_0^\infty e^{-n(s-\log(1+s)}\,\mathrm{d}s\\ &=n^{n+1}e^{-n}\int_0^\infty e^{-nu^2/2}\,s’\,\mathrm{d}u\tag{4} \end{align}
where $t=n(s+1)$ and $u^2/2=s-\log(1+s)$.

Note that $\frac{ss’}{1+s}=u$; thus, when $s\ge1$, $s’\le2u$. This leads to the bound
\begin{align} \int_{s\ge1} e^{-nu^2/2}\,s’\,\mathrm{d}u &\le\int_{3/4}^\infty e^{-nu^2/2}\,2u\,\mathrm{d}u\\ &=\frac2ne^{-\frac98n}\tag{5} \end{align}
$(5)$ also show that
$$\int_{s\ge1}e^{-nu^2/2}\,\mathrm{d}u\le\frac2ne^{-\frac98n}\tag{6}$$

For $|s|<1$, we get
$$u^2/2=s-\log(1+s)=s^2/2-s^3/3+s^4/4-\dots\tag{7}$$
We can invert the series to get $s’=1+\frac23u+O(u^2)$. Therefore,
\begin{align} \int_0^\infty e^{-nu^2/2}\,s’\,\mathrm{d}u &=\int_{s\in[0,1]} e^{-nu^2/2}\,s’\,\mathrm{d}u+\color{red}{\int_{s>1} e^{-nu^2/2}\,s’\,\mathrm{d}u}\\ &=\int_0^\infty\left(1+\frac23u\right)e^{-nu^2/2}\,\mathrm{d}u-\color{darkorange}{\int_{s>1}\left(1+\frac23u\right)e^{-nu^2/2}\,\mathrm{d}u}\\ &+\int_0^\infty e^{-nu^2/2}\,O(u^2)\,\mathrm{d}u-\color{darkorange}{\int_{s>1} e^{-nu^2/2}\,O(u^2)\,\mathrm{d}u}\\ &+\color{red}{\int_{s>1} e^{-nu^2/2}\,s’\,\mathrm{d}u}\\ &=\sqrt{\frac{\pi}{2n}}+\frac2{3n}+O\left(n^{-3/2}\right)\tag{8} \end{align}
The red and orange integrals decrease exponentially by $(5)$ and $(6)$.

Plugging $(8)$ into $(4)$ yields
$$\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t=\left(\sqrt{\frac{\pi n}{2}}+\frac23\right)\,n^ne^{-n}+O(n^{n-1/2}e^{-n})\tag{9}$$
The argument above can be used to prove Stirling’s approximation, which says that
$$n!=\sqrt{2\pi n}\,n^ne^{-n}+O(n^{n-1/2}e^{-n})\tag{10}$$
Combining $(9)$ and $(10)$ yields
\begin{align} e^{-n}\sum_{k=0}^n\frac{n^k}{k!} &=\frac{1}{n!}\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t\\ &=\frac12+\frac{2/3}{\sqrt{2\pi n}}+O(n^{-1})\tag{11} \end{align}

If you’d like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf

The sum is related to the partial exponential sum, and thus to the incomplete gamma function,
$$\begin{eqnarray*} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} &=& e^{-n} e_n(n) \\ &=& \frac{\Gamma(n+1,n)}{\Gamma(n+1)}, \end{eqnarray*}$$
since $e_n(x) = \sum_{k=0}^n x^k/k! = e^x \Gamma(n+1,x)/\Gamma(n+1)$.
But
$$\begin{eqnarray*} \Gamma(n+1,n) &=& \sqrt{2\pi}\, n^{n+1/2}e^{-n}\left(\frac{1}{2} + \frac{1}{3}\sqrt{\frac{2}{n\pi}} + O\left(\frac{1}{n}\right) \right). \end{eqnarray*}$$
The first term in the asymptotic expansion for $\Gamma(n+1,n)$ can be found by applying the saddle point method to
$$\Gamma(n+1,n) = \int_n^\infty dt\, t^n e^{-t}.$$
The higher order terms are in principle straightforward to compute.
Using Stirling’s approximation, we find
$$e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} = \frac{1}{2} + \frac{1}{3}\sqrt{\frac{2}{n\pi}} + O\left(\frac{1}{n}\right).$$
Thus, the limit is $1/2$, as found by @sos440 and @robjohn.
This limit is a special case of DLMF 8.11.13.

I just noticed a comment that suggests this be done using high school level math.
If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! 😉

I’ll give you two hints:

1) Poisson distributions;

2) Central limit theorem

I am not aware of any other technique to solve the problem, so any other answer is appreciated.

\begin{align}&\color{#00f}{
\lim_{n \to \infty}\bracks{\expo{-n}\sum_{k = 0}^{n}{n^{k} \over k!}}}
\\[3mm]&=\lim_{n \to \infty}\bracks{\expo{-n}\sum_{k = 0}^{n}
\exp\pars{k\ln\pars{n} – \ln\pars{k!}}}
\\[3mm]&=
\lim_{n \to \infty}\braces{\expo{-n}\sum_{k = 0}^{n}
\exp\pars{n\ln\pars{n} – \ln\pars{n!} – {1 \over 2n}\bracks{k – n}^{2}}}
\\[3mm]&=
\lim_{n \to \infty}\braces{\expo{-n}\,{n^{n} \over n!}\sum_{k = 0}^{n}
\exp\pars{-{1 \over 2n}\bracks{k – n}^{2}}}
\\[3mm]&=
\lim_{n \to \infty}\braces{{\expo{-n}n^{n} \over n!}\int_{0}^{n}
\exp\pars{-{1 \over 2n}\bracks{k – n}^{2}}\,\dd k}
\\[3mm]&=
\lim_{n \to \infty}\bracks{{\expo{-n}n^{n} \over n!}\int_{-n}^{0}
\exp\pars{-\,{k^{2} \over 2n}}\,\dd k}
=
\lim_{n \to \infty}\bracks{{\expo{-n}n^{n} \over n!}\,\root{2n}
\int_{-\root{n}/2}^{0}\exp\pars{-k^{2}}\,\dd k}
\\[3mm]&=
\lim_{n \to \infty}\bracks{{\root{2}n^{n + 1/2}\expo{-n} \over n!}
\int_{-\infty}^{0}\exp\pars{-k^{2}}\,\dd k}
=
\lim_{n \to \infty}\bracks{{\root{2}n^{n + 1/2}\expo{-n} \over n!}
\,{\root{\pi} \over 2}}
\\[3mm]&=
\half\,\lim_{n \to \infty}\bracks{{\root{2\pi}n^{n + 1/2}\expo{-n} \over n!}}
=\color{#00f}{\Large\half}
\end{align}

For a given $n$, the result is $\dfrac{\Gamma(n+1,n)}{n\ \Gamma(n)}$ which has a limit equal to $\dfrac12$ as $n\to\infty$.