Vrftjkry

Prove that $$limlimits_{ntoinfty} 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 $limlimits_{ntoinfty}(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.

The answer by Sangchul Lee was written for the first version of this question which was not filled with details, for what I am sorry, and hence his answer does not answer my question.

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

Every solution 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.

Elementary proof. 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 $ntoinfty$.

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

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) = leftlceil n^{(1+alpha)/2} rightrceil$. 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)
= expleft{ -frac{p^2}{2n} + mathcal{O}left( n^{-(1-3alpha)/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

$$ maxBigg{ 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 $ntoinfty$, since $sum_{p=1}^{N} e^{-frac{p^2}{2n}} geq sqrt{n} , e^{-1/2} to infty$ as $ntoinfty$. (In fact, this sum is $(1+o(1))sqrt{pi n/2}$ as $ntoinfty$.)

Only a comment.

I also use Stirling and (a Riemann) integral, but in a short way as a rough method.

$displaystyle e^{-n}sumlimits_{k=0}^nfrac{n^k}{k!} = e^{-n}sumlimits_{k=0}^nfrac{k^k (n-k)^{n-k}}{k!(n-k)!} $

$displaystyle asymp e^{-n}sumlimits_{k=1}^{n-1}frac{e^k e^{n-k}}{sqrt{2pi k (1+mathcal{O}(1/k))}sqrt{2pi (n-k)(1+mathcal{O}(1/(n-k)))}} $

$displaystyle asymp frac{1}{2pi}frac{1}{n}sumlimits_{k=1}^{n-1}frac{1}{sqrt{frac{k}{n}left(1-frac{k}{n}right)}} asymp frac{1}{2pi} intlimits_0^1frac{dx}{sqrt{x(1-x)}} = frac{1}{2}$

Note: I use $asymp$ for "same asymptotically" in terms of $ntoinfty$ .

Maybe someone has an idea, how to simplify that, so that $pi$ and the integral disappear ?!