# $\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} = \frac{1}{2}$ - basic methods

Prove that $$\lim\limits_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} = \frac{1}{2}$$

This problem appeared on MSE many times, but each time it was solved using Poisson distribution or lots of integrals. I am wondering, is there any way to prove it using some basic properties of limits (their arithmetics, squeeze theorem etc.), definition of $$e^x$$ as $$\lim\limits_{n\to\infty}(1+\frac{x}{n})^n$$, basic limits with $$e$$, binomial expansion and logarithms, but without using integrals, series, Stirling formula, asymptotics, Taylor series?

This problem was given to me by my mathematical analysis teacher, but it's not a homework, just additional problem to think on. My teacher claims it can be solved with knowledge introduced on lectures so far, which is not much, mainly things mentioned above. Of course, I can use theorems not mentioned on the lectures, but then I have to prove them, and again, with the baisc knowledge. I've been thinking about it for a few days and couldn't do any major progress in my attempts.

• Previous times this question has been asked: math.stackexchange.com/questions/2603315/…, math.stackexchange.com/questions/160248/… . I'm not flagging as duplicate because the question specifically asks for basic methods. Nov 15 '18 at 23:42
• Interestingly, the general term $n^k/k!$ is maximum when $k=n$. And by some magic, the sum "before" equals the sum "after" (asymptotically).
– user65203
Nov 18 '18 at 13:12
• Without an algebraic miracle, I do not think there is a simple and rigorous solution. My rationale is that any solution should demonstrate the understanding on the concentration behavior of the function $k \mapsto \frac{n^k}{k!}e^{-n}$ around $k = n$. Both the probabilistic solution (using Poisson distribution + CLT) and the solution using integral show this. My solution is also based on this kind of observation. Nov 18 '18 at 19:16

Table of Content.

1. Heuristic argument
2. Elementary proof, version 1.
3. Elementary proof, version 2. (NEW!)

# 1. Heuristic argument.

Although far from being rigorous, one can provide a heuristic computation which explains why we expect the answer to be $$\frac{1}{2}$$. Notice that

$$\frac{n^{n+j}/(n+j)!}{n^n / n!} = \begin{cases} \prod_{k=1}^{j} \frac{n}{n+k}, & j \geq 1 \\ 1, & j = 0, -1 \\ \prod_{k=1}^{-j-1} \frac{n-k}{n}, & j \leq -2 \end{cases}$$

In any of cases, taking logarithm and applying the approximation $$\log(1+x) \approx x$$ shows that the above quantity is approximately $$e^{-j^2/2n}$$. So

$$e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} = \frac{\sum_{j=-n}^{0} \frac{n!}{n^n \sqrt{n}} \frac{n^{n+j}}{(n+j)!} }{\sum_{j=-n}^{\infty} \frac{n!}{n^n \sqrt{n}}\frac{n^{n+j}}{(n+j)!} } \approx \frac{\sum_{j=-n}^{0} e^{-(j/\sqrt{n})^2/2} \frac{1}{\sqrt{n}} }{\sum_{j=-n}^{\infty} e^{-(j/\sqrt{n})^2/2} \frac{1}{\sqrt{n}} } \approx \frac{\int_{-\infty}^{0} e^{-x^2/2} \, dx}{\int_{-\infty}^{\infty} e^{-x^2/2} \, dx} = \frac{1}{2}.$$

Most of the solutions that I know is more or less a rigorous realization of this kind of observation, and so, it is either involved or requiring extra knowledge.

# 2. Elementary proof, version 1.

Define $$A_n$$, $$B_n$$ and $$C_n$$ by

$$A_n := e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}, \qquad B_n := e^{-n} \sum_{k=n+1}^{\infty} \frac{n^k}{k!}, \qquad C_n = \frac{n^{n} e^{-n}}{n!}.$$

From the Taylor expansion of the exponential function, we know that $$A_n + B_n = 1$$. In order to show the desired convergence, it suffices to show that the following claim holds.

Claim. $$A_n/B_n \to 1$$ as $$n\to\infty$$.

Indeed, once this is proved, then both $$A_n$$ and $$B_n$$ converge to $$\frac{1}{2}$$ as $$n\to\infty$$.

Proof of Claim. Using the substitution $$k = n-j$$ followed by $$p = j-1$$, one may write

\begin{align*} \frac{A_n}{C_n} &= \sum_{j=0}^{n} \frac{n!}{(n-j)!n^j} = 2 + \sum_{p=1}^{n-1} \prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right). \end{align*}

Similarly, applying the substitution $$k = n+p$$, one may write

\begin{align*} \frac{B_n}{C_n} &= \sum_{p=1}^{\infty} \frac{n!n^p}{(n+p)!} = \sum_{p=1}^{\infty} \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right). \end{align*}

1. Estimation of leading sums. Fix $$\alpha \in \left( 0, \frac{1}{3} \right)$$ and set $$N = N(\alpha) = \left\lceil n^{(1+\alpha)/2} \right\rceil$$. Then using the asymptotic formula $$1+x = e^{x+\mathcal{O}(x^2)}$$ as $$x \to 0$$, for $$1 \leq p \leq N$$ we have

$$\prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right) = \exp\left\{ -\frac{p^2}{2n} + \mathcal{O}\left( n^{-(1-3\alpha)/2} \right) \right\} = \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right).$$

In particular, there exists a constant $$C > 0$$, depending only on $$\alpha$$, such that

$$\max\Bigg\{ \prod_{l=1}^{N} \left( 1 - \frac{l}{n} \right), \prod_{l=1}^{N} \left( \frac{1}{1 + \frac{l}{n}} \right) \Bigg\} \leq C e^{-\frac{1}{2}n^{\alpha}}.$$

2. Estimation of tail sums. In this time, consider $$p > N$$. Then we have

$$\prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right) \leq C e^{-\frac{1}{2}n^{\alpha}} \left( 1 - \frac{N}{n} \right)^{p-N} \quad \text{and} \quad \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right) \leq C e^{-\frac{1}{2}n^{\alpha}} \left( \frac{1}{1 + \frac{N}{n}} \right)^{p-N}.$$

So the tail sum for $$A_n/C_n$$ can be bounded from above by

$$\sum_{p=N+1}^{n-1} \prod_{l=1}^{p} \left( 1 - \frac{l}{n} \right) \leq Ce^{-\frac{1}{2}n^{\alpha}} \sum_{k = 0}^{\infty} \left( 1 - \frac{N}{n} \right)^k \leq \frac{Cn}{N} e^{-\frac{1}{2}n^{\alpha}} \leq Cn^{(1-\alpha)/2} e^{-\frac{1}{2}n^{\alpha}},$$

and likewise,

$$\sum_{p=N+1}^{\infty} \prod_{l=1}^{p} \left( \frac{1}{1 + \frac{l}{n}} \right) \leq Ce^{-\frac{1}{2}n^{\alpha}} \sum_{k = 0}^{\infty} \left( 1 - \frac{N}{N+n} \right)^k \leq \frac{2Cn}{N} e^{-\frac{1}{2}n^{\alpha}} \leq 2Cn^{(1-\alpha)/2} e^{-\frac{1}{2}n^{\alpha}}.$$

3. Conclusion. Combining altogether,

$$\frac{A_n}{B_n} = \frac{\left( 1 + o(1) \right) \sum_{p=1}^{N} e^{-\frac{p^2}{2n}} + \mathcal{O}(1)}{\left( 1 + o(1) \right) \sum_{p=1}^{N} e^{-\frac{p^2}{2n}} + o(1)},$$

which can be easily shown to converge to $$1$$ as $$n\to\infty$$, since $$\sum_{p=1}^{N} e^{-\frac{p^2}{2n}} \geq \sqrt{n} \, e^{-1/2} \to \infty$$ as $$n\to\infty$$. (In fact, this sum is $$(1+o(1))\sqrt{\pi n/2}$$ as $$n\to\infty$$.)

# 3. Elementary proof, version 2.

In this answer, we do appeal to the concentration behavior of the sum, but rather utilize a mysterious identity from combinatorics.

Write $$A_n = e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$$ for the sequence of our interest. We also introduce the following auxiliary sequences:

$$a_n = \frac{n^n}{n!e^n}, \qquad b_n = (-1)^n \binom{-1/2}{n} = \frac{1}{4^n} \binom{2n}{n},$$

Before proceeding, we make some observations. The key ingredients are the following identities

$$A_n = \sum_{k=0}^{n} a_k a_{n-k}, \qquad 1 = \sum_{k=0}^{n} b_k b_{n-k}.$$

The former one is quite non-trivial, and a proof can be found here. On the other hand, the latter one is easily proved by comparing both sides of $$\sum_{n=0}^{\infty} x^n = \frac{1}{1-x} = \left( \frac{1}{\sqrt{1-x}} \right)^2 = \left( \sum_{n=0}^{\infty} b_n x^n \right)^2$$. Next, we have the following observation.

Lemma. $$\frac{a_n}{b_n} \to \frac{1}{\sqrt{2}}$$ as $$n\to\infty$$.

This lemma tells that, roughly $$a_{k}a_{n-k} \approx \frac{1}{2} b_k b_{n-k}$$ and hence $$A_n \approx \frac{1}{2} \sum_{k=0}^{n} b_k b_{n-k} = \frac{1}{2}$$. Indeed, this is an instance of the philosophy that `limit should be preserved under averaging', and so, it can be proved by a standard machinery. We separate the rigorous claim into a standalone result:

Proposition. Let $$(a_n), (b_n)$$ be sequences in $$(0, \infty)$$ such that

1. $$a_n/b_n \to \ell \in (0, \infty)$$;
2. $$b_n \to 0$$ as $$n\to\infty$$;
3. $$\sum_{k=0}^{n} b_k b_{n-k} = 1$$ for all $$n$$.

Then $$\sum_{k=0}^{n} a_k a_{n-k} \to \ell^2$$ as $$n\to\infty$$.

Therefore, $$A_n \to \frac{1}{2}$$ is a direct consequence of this proposition together with the well-known fact that $$b_n \to 0$$. Indeed, this can be proved as follows:

$$b_n^2 = \left( \frac{1 \cdot 3 \cdots (2n-1)}{2 \cdot 4 \cdots (2n)} \right)^2 = \left( \frac{1 \cdot 3}{2 \cdot 2} \right) \left( \frac{3 \cdot 5}{4 \cdot 4} \right) \cdots \left( \frac{(2n-3)(2n-1)}{(2n-2)(2n-2)} \right) \frac{2n-1}{4n^2} \leq \frac{1}{2n}.$$

Finally, we prove the claims above.

• Proof of Lemma. Using the identity $$-\int_{0}^{1} \frac{u}{a+u} \, du = a \log (a+1) - a \log a - 1$$ for $$a > 0$$, we notice that

\begin{align*} &- \sum_{k=1}^{n} \int_{0}^{1} \frac{u}{n+k-1+u} \, du \\ &= \sum_{k=1}^{n} \left[ (n+k-1)\log (n+k) - (n+k-1)\log(n+k-1) - 1 \right] \\ &= (2n)\log(2n) - n \log n - n - \sum_{k=1}^{n} \log(n+k) \\ &= \log \left[ \left( \frac{4n}{e} \right)^n \frac{n!}{(2n)!} \right] = \log \left( \frac{a_n}{b_n} \right). \end{align*}

Then, using $$\frac{1}{2(n+k)} \leq \int_{0}^{1} \frac{u}{n+k-1+u} \, du \leq \frac{1}{2(n+k-1)}$$, we obtain

$$-\frac{1}{2}\sum_{k=1}^{n} \frac{1}{n+k-1} \leq \log \left( \frac{a_n}{b_n} \right) \leq -\frac{1}{2}\sum_{k=1}^{n} \frac{1}{n+k}.$$

Therefore the conclusion follows from the well-known limit $$\sum_{k=1}^{n} \frac{1}{1+\frac{k}{n}} \frac{1}{n} \to \int_{0}^{1} \frac{dx}{1+x} = \log 2$$.

• Proof of Proposition. Let $$\alpha, \beta$$ satisfy $$0 < \alpha < \ell < \beta$$. Then there exists $$N$$ such that $$\alpha \leq \frac{a_n}{b_n} \leq \beta$$ for all $$n \geq N$$. So, if $$n \geq 2N$$, then

$$\alpha^2 \sum_{k=N}^{n-N} b_k b_{n-k} \leq \sum_{k=N}^{n-N} a_k a_{n-k} \leq \beta^2 \sum_{k=N}^{n-N} b_k b_{n-k}.$$

Now let $$M > 0$$ be a bound of $$a_n/b_n$$. Since $$b_n \to 0$$ as $$n\to\infty$$, we have

$$\sum_{k=0}^{N-1} a_k a_{n-k} + \sum_{k=n-N+1}^{n} a_k a_{n-k} = 2\sum_{k=0}^{N-1} a_k a_{n-k} \leq 2M^2 \sum_{k=0}^{N-1} b_k b_{n-k} \xrightarrow[n\to\infty]{} 0$$

Combining altogether and using $$1 = \sum_{k=0}^{n} b_k b_{n-k}$$,

$$\alpha^2 \leq \liminf_{n\to\infty} \sum_{k=0}^{n} a_k a_{n-k} \leq \limsup_{n\to\infty} \sum_{k=0}^{n} a_k a_{n-k} \leq \beta^2.$$

Letting $$\alpha \uparrow \ell$$ and $$\beta \downarrow \ell$$ proves the desired identity.

We conclude with some remarks.

Remark. If we do not care about elementary solution, this approach can be simplified by showing that

1. $$A_n$$ is bounded and decreasing, hence converges.
2. By the identity $$A_n = \sum_{k=0}^{n} a_k a_{n-k}$$, we have

$$(1-x) \sum_{n=0}^{\infty} A_n x^n = \left( \frac{\sum_{n=0}^{\infty} a_n x^n}{\sum_{n=0}^{\infty} b_n x^n} \right)^2,$$

hence by a version of abelian theorem, we obtain

$$\lim_{n\to\infty} A_n = \lim_{n\to\infty} \left( \frac{a_n}{b_n} \right)^2 = \frac{1}{2}.$$