Sunday, November 8, 2015

real analysis - $lim_{ntoinfty} 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.


Answer



Table of Content.


  1. Heuristic argument


  2. Elementary proof, version 1.

  3. 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


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





No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...