Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm supposed to calculate:

$$\lim_{n\to\infty} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!}$$

By using W|A, i may guess that the limit is $\frac{1}{2}$ that is a pretty interesting and nice result. I wonder in which ways we may approach it.

share|improve this question
1  
How do you formulate this for W|A to get that result? I didn't get it work... –  Gottfried Helms Jun 19 '12 at 9:46
    
@Gottfried Helms: wolframalpha.com/input/?i=%28sum_k%3D0^500+%28%28500^k%29%2Fk!%29*%28‌​e^%28-500%29%29. It seems the limit goes to $\frac{1}{2}$. –  Chris's sis Jun 19 '12 at 9:47
    
hmm, for me W|A says zero for your expression... (where we have the constant 500, why? you can ask for limits, too) What's going on here? –  Gottfried Helms Jun 19 '12 at 9:51
8  
When you write, "I'm supposed to calculate", do you mean this is homework? There's nothing wrong with that, but if it is homework, I'd encourage you to edit in the "homework" tag. –  Gerry Myerson Jun 19 '12 at 9:51
2  
Related: math.stackexchange.com/questions/121099/… –  leonbloy Jun 19 '12 at 15:46
show 6 more comments

8 Answers

up vote 17 down vote accepted

If you'd like to see formal solution using calculus methods check this article http://www.emis.de/journals/AMAPN/vol15/voros.pdf

share|improve this answer
add comment

$\newcommand{\+}{^{\dagger}}% \newcommand{\angles}[1]{\left\langle #1 \right\rangle}% \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}% \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}% \newcommand{\dd}{{\rm d}}% \newcommand{\isdiv}{\,\left.\right\vert\,}% \newcommand{\ds}[1]{\displaystyle{#1}}% \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}% \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}% \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}% \newcommand{\half}{{1 \over 2}}% \newcommand{\ic}{{\rm i}}% \newcommand{\imp}{\Longrightarrow}% \newcommand{\ket}[1]{\left\vert #1\right\rangle}% \newcommand{\pars}[1]{\left( #1 \right)}% \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}}% \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}% \newcommand{\sech}{\,{\rm sech}}% \newcommand{\sgn}{\,{\rm sgn}}% \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}}% \newcommand{\verts}[1]{\left\vert #1 \right\vert}% \newcommand{\yy}{\Longleftrightarrow}$ \begin{align}&\color{#00f}{% \lim_{n \to \infty}\bracks{\expo{-n}\sum_{k = 0}^{n}{n^{k} \over k!}}} \\[3mm]&=\lim_{n \to \infty}\bracks{\expo{-n}\sum_{k = 0}^{n} \exp\pars{k\ln\pars{n} - \ln\pars{k!}}} \\[3mm]&= \lim_{n \to \infty}\braces{\expo{-n}\sum_{k = 0}^{n} \exp\pars{n\ln\pars{n} - \ln\pars{n!} - {1 \over 2n}\bracks{k - n}^{2}}} \\[3mm]&= \lim_{n \to \infty}\braces{\expo{-n}\,{n^{n} \over n!}\sum_{k = 0}^{n} \exp\pars{-{1 \over 2n}\bracks{k - n}^{2}}} \\[3mm]&= \lim_{n \to \infty}\braces{{\expo{-n}n^{n} \over n!}\int_{0}^{n} \exp\pars{-{1 \over 2n}\bracks{k - n}^{2}}\,\dd k} \\[3mm]&= \lim_{n \to \infty}\bracks{{\expo{-n}n^{n} \over n!}\int_{-n}^{0} \exp\pars{-\,{k^{2} \over 2n}}\,\dd k} = \lim_{n \to \infty}\bracks{{\expo{-n}n^{n} \over n!}\,\root{2n} \int_{-\root{n}/2}^{0}\exp\pars{-k^{2}}\,\dd k} \\[3mm]&= \lim_{n \to \infty}\bracks{{\root{2}n^{n + 1/2}\expo{-n} \over n!} \int_{-\infty}^{0}\exp\pars{-k^{2}}\,\dd k} = \lim_{n \to \infty}\bracks{{\root{2}n^{n + 1/2}\expo{-n} \over n!} \,{\root{\pi} \over 2}} \\[3mm]&= \half\,\lim_{n \to \infty}\bracks{{\root{2\pi}n^{n + 1/2}\expo{-n} \over n!}} =\color{#00f}{\Large\half} \end{align}

share|improve this answer
    
The second equal sign is a complete mystery. The passage from a sum to an integral also needs justification but it probably holds. –  Did Mar 31 at 16:25
1  
It seems you developed the habit of downvoting for no reason one or two of my answers, each time I dare point to some defects of your posts, without ever addressing the specific mathematical points I am making. These sneaky ways are just despicable. –  Did Mar 31 at 18:14
add comment

I do not know how much this will help you.

For a given $n$, the result is $\dfrac{\Gamma(n+1,n)}{n\ \Gamma(n)}$ which has a limit equal to $\dfrac12$ as $n\to\infty$.

share|improve this answer
    
Thank you very much. –  mathlove Sep 15 '13 at 15:00
add comment

By simple(?) manipulation,

$$ \begin{align*} e^{-n}\sum_{k=0}^{n} \frac{n^k}{k!} &= \frac{e^{-n}}{n!} \sum_{k=0}^{n}\binom{n}{k} n^k (n-k)! \\ &= \frac{e^{-n}}{n!} \sum_{k=0}^{n}\binom{n}{k}\int_{0}^{\infty} n^k t^{n-k}e^{-t}\;dt\\ &= \frac{e^{-n}}{n!} \int_{0}^{\infty} (n+t)^{n}e^{-t}\;dt\\ &= \frac{n^n e^{-n}}{n!} \int_{0}^{\infty} \left(1+\frac{t}{n}\right)^{n}e^{-t}\;dt. \end{align*}$$

Thus from Stirling's formula, it suffices to show that

$$\frac{1}{\sqrt{2\pi n}} \int_{0}^{\infty} \left(1+\frac{t}{n}\right)^{n}e^{-t}\;dt \xrightarrow{n\to\infty} \frac{1}{2}.$$

Remark that

  1. $2^x \geq 1+x$ for all $x\geq 1$, and
  2. we have $$x - \frac{x^2}{2} \leq \log (1+x) = x - \frac{x^2}{2} +O(x^3) \leq x - \frac{x^2}{6}$$ for $0\leq x \leq 1$.

From this, we first note that

$$\frac{1}{\sqrt{2\pi n}} \int_{n}^{\infty} \left(1+\frac{t}{n}\right)^{n}e^{-t}\;dt \leq \frac{1}{\sqrt{2\pi n}} \int_{n}^{\infty} (e/2)^{-t}\;dt \xrightarrow{n\to\infty} 0.$$

Moreover,

$$ \begin{align*} \frac{1}{\sqrt{2\pi n}} \int_{0}^{n} \left(1+\frac{t}{n}\right)^{n}e^{-t}\;dt &= \frac{1}{\sqrt{2\pi n}} \int_{0}^{n} \exp \left(-\frac{t^2}{2n} + O\left(\frac{t^3}{n^2}\right)\right)\;dt \\ &= \frac{1}{\sqrt{2\pi}} \int_{0}^{\sqrt{n}} \exp \left(-\frac{u^2}{2} + O\left(\frac{u^3}{\sqrt{n}}\right)\right)\;du \quad (t = u\sqrt{n}), \end{align*}$$

Which converges to

$$ \frac{1}{\sqrt{2\pi}} \int_{0}^{\infty} e^{-u^2/2}\;du = \frac{1}{2}$$

by dominated convergence theorem and Gaussian integral. Therefore the limit follows by our observations.

share|improve this answer
7  
Wow! +1 ${}{}{}{}{}{}$ –  Sam Jun 19 '12 at 14:14
    
Your second equation is closely related to this question (which I answered). –  robjohn Jun 19 '12 at 15:47
add comment

Integration by parts yields $$ \frac{1}{k!}\int_x^\infty e^{-t}\,t^k\,\mathrm{d}t=\frac{1}{k!}x^ke^{-x}+\frac{1}{(k-1)!}\int_x^\infty e^{-t}\,t^{k-1}\,\mathrm{d}t\tag{1} $$ Iterating $(1)$ gives $$ \frac{1}{n!}\int_x^\infty e^{-t}\,t^n\,\mathrm{d}t=e^{-x}\sum_{k=0}^n\frac{x^k}{k!}\tag{2} $$ Thus, we get $$ e^{-n}\sum_{k=0}^n\frac{n^k}{k!}=\frac{1}{n!}\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t\tag{3} $$ Now, I will reproduce part of the argument I give here, which develops a full asymptotic expansion. Additionally, I include some error estimates that were previously missing. $$ \begin{align} \int_n^\infty e^{-t}\,t^n\,\mathrm{d}t &=n^{n+1}e^{-n}\int_0^\infty e^{-ns}\,(s+1)^n\,\mathrm{d}s\\ &=n^{n+1}e^{-n}\int_0^\infty e^{-n(s-\log(1+s)}\,\mathrm{d}s\\ &=n^{n+1}e^{-n}\int_0^\infty e^{-nu^2/2}\,s'\,\mathrm{d}u\tag{4} \end{align} $$ where $t=n(s+1)$ and $u^2/2=s-\log(1+s)$.

Note that $\frac{ss'}{1+s}=u$; thus, when $s\ge1$, $s'\le2u$. This leads to the bound $$ \begin{align} \int_{s\ge1} e^{-nu^2/2}\,s'\,\mathrm{d}u &\le\int_{3/4}^\infty e^{-nu^2/2}\,2u\,\mathrm{d}u\\ &=\frac2ne^{-\frac98n}\tag{5} \end{align} $$ $(5)$ also show that $$ \int_{s\ge1}e^{-nu^2/2}\,\mathrm{d}u\le\frac2ne^{-\frac98n}\tag{6} $$

For $|s|<1$, we get $$ u^2/2=s-\log(1+s)=s^2/2-s^3/3+s^4/4-\dots\tag{7} $$ We can invert the series to get $s'=1+\frac23u+O(u^2)$. Therefore, $$ \begin{align} \int_0^\infty e^{-nu^2/2}\,s'\,\mathrm{d}u &=\int_{s\in[0,1]} e^{-nu^2/2}\,s'\,\mathrm{d}u+\color{red}{\int_{s>1} e^{-nu^2/2}\,s'\,\mathrm{d}u}\\ &=\int_0^\infty\left(1+\frac23u\right)e^{-nu^2/2}\,\mathrm{d}u-\color{darkorange}{\int_{s>1}\left(1+\frac23u\right)e^{-nu^2/2}\,\mathrm{d}u}\\ &+\int_0^\infty e^{-nu^2/2}\,O(u^2)\,\mathrm{d}u-\color{darkorange}{\int_{s>1} e^{-nu^2/2}\,O(u^2)\,\mathrm{d}u}\\ &+\color{red}{\int_{s>1} e^{-nu^2/2}\,s'\,\mathrm{d}u}\\ &=\sqrt{\frac{\pi}{2n}}+\frac2{3n}+O\left(n^{-3/2}\right)\tag{8} \end{align} $$ The red and orange integrals decrease exponentially by $(5)$ and $(6)$.

Plugging $(8)$ into $(4)$ yields $$ \int_n^\infty e^{-t}\,t^n\,\mathrm{d}t=\left(\sqrt{\frac{\pi n}{2}}+\frac23\right)\,n^ne^{-n}+O(n^{n-1/2}e^{-n})\tag{9} $$ The argument above can be used to prove Stirling's approximation, which says that $$ n!=\sqrt{2\pi n}\,n^ne^{-n}+O(n^{n-1/2}e^{-n})\tag{10} $$ Combining $(9)$ and $(10)$ yields $$ \begin{align} e^{-n}\sum_{k=0}^n\frac{n^k}{k!} &=\frac{1}{n!}\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t\\ &=\frac12+\frac{2/3}{\sqrt{2\pi n}}+O(n^{-1})\tag{11} \end{align} $$

share|improve this answer
add comment

The probabilistic way:

This is $P[N_n\leqslant n]$ where $N_n$ is a random variable with Poisson distribution of parameter $n$. Hence each $N_n$ is distributed like $X_1+\cdots+X_n$ where the random variables $(X_k)$ are independent and identically distributed with Poisson distribution of parameter $1$.

By the central limit theorem, $Y_n=\frac1{\sqrt{n}}(X_1+\cdots+X_n-n)$ converges in distribution to a standard normal random variable $Z$, in particular, $P[Y_n\leqslant 0]\to P[Z\leqslant0]$.

Finally, $P[Z\leqslant0]=\frac12$ and $[N_n\leqslant n]=[Y_n\leqslant 0]$ hence $P[N_n\leqslant n]\to\frac12$, QED.


The analytical way, completing your try:

Hence, I know that what I need to do is to find $\lim\limits_{n\to\infty}I_n$, where $$ I_n=\frac{e^{-n}}{n!}\int_{0}^n (n-t)^ne^tdt.$$

To begin with, let $u(t)=(1-t)e^t$, then $I_n=\dfrac{e^{-n}n^n}{n!}nJ_n$ with $$ J_n=\int_{0}^1 u(t)^n\mathrm dt. $$ Now, $u(t)\leqslant\mathrm e^{-t^2/2}$ hence $$ J_n\leqslant\int_0^1\mathrm e^{-nt^2/2}\mathrm dt\leqslant\int_0^\infty\mathrm e^{-nt^2/2}\mathrm dt=\sqrt{\frac{\pi}{2n}}. $$ Likewise, the function $t\mapsto u(t)\mathrm e^{t^2/2}$ is decreasing on $t\geqslant0$ hence $u(t)\geqslant c_n\mathrm e^{-t^2/2}$ on $t\leqslant1/n^{1/4}$, with $c_n=u(1/n^{1/4})\mathrm e^{-1/(2\sqrt{n})}$, hence $$ J_n\geqslant c_n\int_0^{1/n^{1/4}}\mathrm e^{-nt^2/2}\mathrm dt=\frac{c_n}{\sqrt{n}}\int_0^{n^{1/4}}\mathrm e^{-t^2/2}\mathrm dt=\frac{c_n}{\sqrt{n}}\sqrt{\frac{\pi}{2}}(1+o(1)). $$ Since $c_n\to1$, all this proves that $\sqrt{n}J_n\to\sqrt{\frac\pi2}$. Stirling formula shows that the prefactor $\frac{e^{-n}n^n}{n!}$ is equivalent to $\frac1{\sqrt{2\pi n}}$. Regrouping everything, one sees that $I_n\sim\frac1{\sqrt{2\pi n}}n\sqrt{\frac\pi{2n}}=\frac12$.


Moral:

The probabilistic way is shorter, easier, more illuminating (and more fun). Caveat: my advice in these matters is (as one can see) horribly biased.

share|improve this answer
    
Thanks. Deleting. –  Pedro Tamaroff Sep 14 '13 at 15:44
2  
+1 your moral and the caveat. –  Lost1 Dec 30 '13 at 23:55
add comment

The sum is related to the partial exponential sum, and thus to the incomplete gamma function, $$\begin{eqnarray*} e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} &=& e^{-n} e_n(n) \\ &=& \frac{\Gamma(n+1,n)}{\Gamma(n+1)}, \end{eqnarray*}$$ since $e_n(x) = \sum_{k=0}^n x^k/k! = e^x \Gamma(n+1,x)/\Gamma(n+1)$. But $$\begin{eqnarray*} \Gamma(n+1,n) &=& \sqrt{2\pi}\, n^{n+1/2}e^{-n}\left(\frac{1}{2} + \frac{1}{3}\sqrt{\frac{2}{n\pi}} + O\left(\frac{1}{n}\right) \right). \end{eqnarray*}$$ The first term in the asymptotic expansion for $\Gamma(n+1,n)$ can be found by applying the saddle point method to $$\Gamma(n+1,n) = \int_n^\infty dt\, t^n e^{-t}.$$ The higher order terms are in principle straightforward to compute. Using Stirling's approximation, we find $$e^{-n} \sum_{k=0}^{n} \frac{n^k}{k!} = \frac{1}{2} + \frac{1}{3}\sqrt{\frac{2}{n\pi}} + O\left(\frac{1}{n}\right).$$ Thus, the limit is $1/2$, as found by @sos440 and @robjohn. This limit is a special case of DLMF 8.11.13.

I just noticed a comment that suggests this be done using high school level math. If this is a standard exercise at your high school, maybe they covered the incomplete gamma function! ;-)

share|improve this answer
2  
(+1) I derived this asymptotic expansion here in answer to a question on sci.math. I computed a few terms past $\frac12$: $$ \frac12+\frac{1}{\sqrt{2\pi n}}\left(\frac23-\frac{23}{270n}+\frac{23}{3024n^2}+\dots\right) $$ –  robjohn Jun 20 '12 at 3:14
    
@robjohn: Thanks for the link, I'll have a look. By the way, I voted up your nice solution a couple of hours ago. I like your short and sweet derivation of (3). –  user26872 Jun 20 '12 at 3:47
    
@Chris: Glad to help. And if you find an elementary proof first, make sure to post it! :-) –  user26872 Jun 20 '12 at 5:59
add comment

I'll give you two hints:

1) Poisson distributions;

2) Central limit theorem

I am not aware of any other technique to solve the problem, so any other answer is appreciated.

share|improve this answer
3  
In what country's education system is this a high school exercise?! I ask sincerely because I'm interested in that, and my experience is that even some of the most advanced mathematically education systems don't reach exercises as the one you're proposing...not even close. Of course, I don't know all the education systems (not even close, again), but the expression within the sum seems to be pretty tough...it reminds the series for the exponential function, but that n repeating in the numerator and upper limit...are you sure the expression is accurate? –  DonAntonio Jun 19 '12 at 10:17
1  
This problem is definitely not at high-school level. Without the hints I gave, I doubt most university students (even graduates) would solve it in reasonable time. –  D. Thomine Jun 19 '12 at 10:43
2  
@Chris, thank you for checking. As D. Thomine says, this seems to be ("seems" because I accept the possibility someone else come up with some trick that'll make the solution to your problem embarrasingly easy...) a rather tough exercise, so if you're a high school student I think you shouldn't be too hard on yourself if you are having a rough time tackling this little beast, even with the given hints, which definitely are university level. –  DonAntonio Jun 19 '12 at 10:48
    
The solution using Poisson distribution was also given here: Limit using Poisson distribution –  Martin Sleziak Jun 19 '12 at 15:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.