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.
Table of Content.
- Heuristic argument
- Elementary proof, version 1.
- Elementary proof, version 2. (NEW!)
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.
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$.)
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
- $a_n/b_n \to \ell \in (0, \infty)$;
- $b_n \to 0$ as $n\to\infty$;
- $\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
- $A_n$ is bounded and decreasing, hence converges.
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}. $$
