# Evaluate the limit $\lim\limits_{n\to\infty}{\frac{n!}{n^n}\bigg(\sum_{k=0}^n{\frac{n^{k}}{k!}}-\sum_{k=n+1}^{\infty}{\frac{n^{k}}{k!}}\bigg)}$

Evaluate the limit $$\lim_{n\rightarrow\infty}{\frac{n!}{n^{n}}\left(\sum_{k=0}^{n}{\frac{n^{k}}{k!}}-\sum_{k=n+1}^{\infty}{\frac{n^{k}}{k!}} \right)}$$

I use $$e^{n}=1+n+\frac{n^{2}}{2!}+\cdots+\frac{n^{n}}{n!}+\frac{1}{n!}\int_{0}^{n}{e^{x}(n-x)^{n}dx}$$ but I don't know how to evaluate $$\lim_{n\rightarrow\infty}{\frac{n!}{n^{n}}\left(e^{n}-2\frac{1}{n!}\int_{0}^{n}{e^{x}(n-x)^{n}dx} \right) }$$

-
I guess the second part converges to zero, and for the first part i would use stirling, but that would mean it diverges – Dominic Michaelis Mar 8 '13 at 8:09
The answer is $\frac{4}{3}$, which we can prove by utilizing rlgordonma's calculation. – Sangchul Lee Mar 8 '13 at 8:27

In this answer, it is shown, using integration by parts, that $$\sum_{k=0}^n\frac{n^k}{k!}=\frac{e^n}{n!}\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t\tag{1}$$ Subtracting both sides from $e^n$ gives $$\sum_{k=n+1}^\infty\frac{n^k}{k!}=\frac{e^n}{n!}\int_0^n e^{-t}\,t^n\,\mathrm{d}t\tag{2}$$ Substtuting $t=n(s+1)$ and $u^2/2=s-\log(1+s)$ gives us \begin{align} \Gamma(n+1) &=\int_0^\infty t^n\,e^{-t}\,\mathrm{d}t\\ &=n^{n+1}e^{-n}\int_{-1}^\infty e^{-n(s-\log(1+s))}\,\mathrm{d}s\\ &=n^{n+1}e^{-n}\int_{-\infty}^\infty e^{-nu^2/2}\,s'\,\mathrm{d}u\tag{3} \end{align} and \begin{align} \Gamma(n+1,n) &=\int_n^\infty t^n\,e^{-t}\,\mathrm{d}t\\ &=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} Computing the series for $s'$ in terms of $u$ gives $$s'=1+\frac23u+\frac1{12}u^2-\frac2{135}u^3+\frac1{864}u^4+\frac1{2835}u^5-\frac{139}{777600}u^6+O(u^7)\tag{5}$$ In the integral for $\Gamma(n+1)$, the odd powers of $u$ in $(5)$ are cancelled and the even powers of $u$ are integrated over twice the domain as in the integral for $\Gamma(n+1,n)$. Thus, \begin{align} 2\Gamma(n+1,n)-\Gamma(n+1) &=\int_n^\infty t^n\,e^{-t}\,\mathrm{d}t-\int_0^n t^n\,e^{-t}\,\mathrm{d}t\\ &=n^{n+1}e^{-n}\int_0^\infty e^{-nu^2/2}\,2\,\mathrm{odd}(s')\,\mathrm{d}u\\ &=n^{n+1}e^{-n}\left(\frac4{3n}-\frac8{135n^2}+\frac{16}{2835n^3}+O\left(\frac1{n^4}\right)\right)\\ &=n^ne^{-n}\left(\frac43-\frac8{135n}+\frac{16}{2835n^2}+O\left(\frac1{n^3}\right)\right)\tag{6} \end{align} Therefore, combining $(1)$, $(2)$, and $(6)$, we get \begin{align} \frac{n!}{n^n}\left(\sum_{k=0}^n\frac{n^k}{k!}-\sum_{k=n+1}^\infty\frac{n^k}{k!}\right) &=\frac{e^n}{n^n}\left(\int_n^\infty e^{-t}\,t^n\,\mathrm{d}t-\int_0^n e^{-t}\,t^n\,\mathrm{d}t\right)\\ &=\frac43-\frac{8}{135n}+\frac{16}{2835n^2}+O\left(\frac1{n^3}\right)\tag{7} \end{align}

-

We can write that integral as

$$\int_0^n dx \: e^x (n-x)^n = n^{n+1} \int_0^1 du \: e^{n u} (1-u)^n = n^{n+1}\int_0^1 du \: e^{n [u+\log(1-u)]}$$

Now, as $n \rightarrow \infty$, that last integral is dominated by contributions near $u=0$. We may then use the first term in the Taylor expansion of the exponential, and the integral is, to lowest order of approximation

$$n^{n+1} \int_0^{\infty} du e^{-n u^2/2} = n^{n+1} \sqrt{\frac{2 \pi}{n}}$$

Use Stirling's approximation to get the rest of the story.

EDIT

It was pointed out that we will need to go to the next order of approximation. In this case, use $u+\log{(1-u)} \approx -u^2/2-u^3/3$. We then get, as an approximation to the integral

$$n^{n+1} \int_0^{\infty} du e^{-n u^2/2} e^{-n u^3/3}$$

Note that, form the lowest order of approximation, we are only considering $u \sim 1/\sqrt{n}$. This means that $n u^3 \sim 1/\sqrt{n}$ and we can Taylor expand this exponential for small argument to get the approximation

$$n^{n+1} \int_0^{\infty} du\: e^{-n u^2/2} \left (1-\frac{n u^3}{3}\right) = n^{n+1} \left (\sqrt{\frac{2 \pi}{n}} - \frac{2}{3 n} \right )$$

-
This approach will work, but it's necessary to go beyond the lowest order of approximation for the integral and use both the $u^2/2$ and $u^3/3$ terms in the series for $\log (1-u)$. – David Moews Mar 8 '13 at 9:02
@DavidMoews: fortunately, that is straightforward, as I will show above. – Ron Gordon Mar 8 '13 at 9:15