$\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.

Solution 1:

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}. $$