How to solve this limit with factorial? $\lim_{n\to \infty}\frac{n!}{n^n}(\sum_{k=0}^n\frac{n^k}{k!}-\sum_{k=n+1}^\infty \frac{n^k}{k!})$

Question

I want to solve the limit $$\lim_{n\to \infty}\frac{n!}{n^n}\left(\sum_{k=0}^n\frac{n^k}{k!}-\sum_{k=n+1}^\infty \frac{n^k}{k!}\right)$$ This problem may be about Stirling's Approximation and Taylor series of exponent functions.

As $n$ is big enough, according to Stirling's approximation, $$ n!\approx\sqrt{2\pi n}\frac{n^n}{e^n} $$ and according to Taylor series, $$ \sum_{k=0}^\infty\frac{n^k}{k!}=e^n $$ The difference is the minus instead of the plus of the first $n$ term and the remainder.

I have tried to use the Taylor expansion with an integral remainder, $$ e^n=\sum_{k=0}^n\frac{n^k}{k!}+\int_0^n\frac{(n-t)^n}{n!}e^t\mathrm{d}t $$ so we have the remainder as $$ \sum_{k=n+1}^n\frac{n^k}{k!}=\int_0^n\frac{(n-t)^n}{n!}e^t\mathrm{d}t $$ and the first $n$ term as $$ \sum_{k=0}^n\frac{n^k}{k!}=e^n-\int_0^n\frac{(n-t)^n}{n!}e^t\mathrm{d}t $$ Therefore, we have \begin{aligned} \frac{n!}{n^n}(\sum_{k=0}^n\frac{n^k}{k!}-\sum_{k=n+1}^\infty \frac{n^k}{k!}) &=\frac{n!}{n^n}\left(e^n-2\int_0^n\frac{(n-t)^n}{n!}e^t\mathrm{d}t\right)\\ &=\frac{n!e^n}{n^n}\left(1-2\int_0^n\frac{(n-t)^n}{n!}e^{-(n-t)} \mathrm{d}t\right)\\ &=\frac{n!e^n}{n^n}\left(1-\frac{2}{n!}\int_{0}^n s^ne^{-s}\mathrm{d}s\right)\\ &=\frac{n!e^n}{n^n}\left(1-\frac{2}{n!}\gamma(n+1,n)\right)\\ &\approx \sqrt{2\pi n}\left(1-\frac{2}{n!}\gamma(n+1,n)\right)\\ \end{aligned} where the lower incomplete gamma function $$ \gamma(n+1,n)=\int_{0}^n t^n e^{-t}\mathrm{d}t $$ But how to continue? And I also plot the scattering points of the series, we can see the limit is near 1.333 maybe.

How to continue the calculation and what is the limit?

Answer 1

In this solution, we will prove that the limit is $4/3$ only using an elementary analysis. Let

$$ \bbox[background:#efffe0;padding:5px;]{S_n} = \frac{n!}{n^n} \left(\sum_{k=0}^{n}\frac{n^k}{k!} - \sum_{k=n+1}^{\infty} \frac{n^k}{k!}\right). $$

Then using OP's observation and the Stirling approximation,

\begin{align*} S_n &= \frac{n!}{n^n} \left( e^n - 2 \int_{0}^{n} \frac{(n-t)^n}{n!} e^{t} \, \mathrm{d}t \right) \\ &= \frac{n!}{n^n e^{-n}} - 2 \int_{0}^{n} \left(1 - \frac{t}{n}\right)^n e^{t} \, \mathrm{d}t \\ \quad &= \bigl( \sqrt{2\pi n} + o(1) \bigr) - 2 \sqrt{n} \bbox[background:#efffe0;padding:5px;]{ \underbrace{\int_{0}^{\sqrt{n}} \left(1 - \frac{s}{\sqrt{n}}\right)^n e^{\sqrt{n}s} \, \mathrm{d}s}_{=:I_n} }. \tag{$t = \sqrt{n}s$} \end{align*}

Let's analyze the behavior of $I_n$. To this end, define $ \bbox[background:#efffe0;padding:5px;]{\phi_n(s)} = n\log\bigl(1-\frac{s}{\sqrt{n}}\bigr) + \sqrt{n}s $. Then $I_n$ is recast as $I_n = \int_{0}^{\sqrt{n}} e^{\phi_n(s)} \, \mathrm{d}s$. Now we will make several observation.

$\text{(1)}$ Using the Maclaurin series of $\log(1-x)$, we find that $\phi_n(s) \leq -\frac{s^2}{2}$ holds for $0 \leq s \leq \sqrt{n}$. So, for any $0 < a \leq \sqrt{n}$, we have

$$ \int_{a}^{n} e^{\phi_n(s)} \, \mathrm{d}s \leq \int_{a}^{n} e^{-s^2/2} \, \mathrm{d}s \leq \int_{a}^{\infty} \frac{s}{a} e^{-s^2/2} \, \mathrm{d}s = \frac{1}{a}e^{-s^2/2}. \tag{1} $$

$\text{(2)}$ Define $ \bbox[background:#efffe0;padding:5px;]{\varepsilon_n(s)} := \phi_n(s) + \frac{s^2}{2} - \log\left(1-\frac{s^3}{3\sqrt{n}}\right) $. Using the Maclaurin series of $\log(1-x)$ again, for $1 < a < \frac{1}{2}n^{1/6}$ and $0 \leq s \leq a$, we have

$$ \left|\varepsilon_n(s)\right| \leq n \sum_{k=4}^{\infty} \frac{s^k}{k n^{k/2}} + \sum_{l=2}^{\infty} \frac{s^{3l}}{3l n^{l/2}} \leq \frac{Ca^6}{n}. \tag{2} $$

for some absolute constant $C \in (0, \infty)$.

$\text{(3)}$ By integration by parts, we have $$ \int_{a}^{\infty} s^3 e^{-s^2/2} \, \mathrm{d}s = (a^2+2)e^{-a^2/2} \tag{3} $$

To utilize these observations, we fix a sequence $(a_n)$ satisfying $\bbox[background:#efffe0;padding:5px;]{\sqrt{\log n} \ll a_n \ll n^{1/12}}$. (Here, $f(n) \ll g(n)$ means that $f(n) > 0$, $g(n) > 0$, and $f(n)/g(n) \to 0$ as $n\to\infty$.) For example, we can choose $(a_n)$ so that $a_n = \log n$ for large $n$. Then for sufficiently large $n$,

\begin{align*} I_n &= \int_{0}^{a_n} e^{\phi_n(s)} \, \mathrm{d}s + \mathcal{O}\biggl(\frac{e^{-a_n^2/2}}{a_n}\biggr) \tag{using (1)} \\ &= \int_{0}^{a_n} e^{-s^2/2}\left(1-\frac{s^3}{3\sqrt{n}}\right)e^{\varepsilon_n(s)} \, \mathrm{d}s + \mathcal{O}(a_n^{-1}e^{-a_n^2/2}) \tag{by def. of $\varepsilon_n$} \\ &= e^{\mathcal{O}(a_n^6/n)} \int_{0}^{a_n} e^{-s^2/2}\left(1-\frac{s^3}{3\sqrt{n}}\right) \, \mathrm{d}s + \mathcal{O}(a_n^{-1}e^{-a_n^2/2}) \tag{by (2)} \\ &= e^{\mathcal{O}(a_n^6/n)} \int_{0}^{\infty} e^{-s^2/2}\left(1-\frac{s^3}{3\sqrt{n}}\right) \, \mathrm{d}s + \mathcal{O}\bigl(a_n^2 e^{-a_n^2/2}\bigr) \tag{by (1) and (3)} \\ &= e^{\mathcal{O}(a_n^6/n)} \left( \sqrt{\frac{\pi}{2}} - \frac{2}{3\sqrt{n}} \right) + \mathcal{O}\bigl(a_n^2 e^{-a_n^2/2}\bigr) \\ &= \sqrt{\frac{\pi}{2}} - \frac{2}{3\sqrt{n}} + \mathcal{O}(a_n^6/n) + \mathcal{O}\bigl(a_n^2 e^{-a_n^2/2}\bigr) \end{align*}

Plugging this back to $S_n$, it follows that

$$ S_n = \frac{4}{3} + \mathcal{O}(a_n^6/\sqrt{n}) + \mathcal{O}\bigl(\sqrt{n} a_n^2 e^{-a_n^2/2}\bigr) + o(1). $$

By the assumption on $(a_n)$, all the error terms vanish as $n \to \infty$, and therefore the desired claim follows.

Answer 2

The limit is $4/3$: we have that \begin{aligned} \frac{n!}{n^n}(\sum_{k=0}^n\frac{n^k}{k!}-\sum_{k=n+1}^\infty \frac{n^k}{k!}) &=\frac{n!}{n^n}(2\sum_{k=0}^n\frac{n^k}{k!}-e^n)\\ &=\frac{n!e^{n}}{n^n}\left(2e^{-n}\sum_{k=0}^n\frac{n^k}{k!}-1\right)\\ &=2\frac{n!e^{n}}{n^n}\left(e^{-n}\sum_{k=0}^n\frac{n^k}{k!}\right)-\sqrt{2\pi n}+o(1)\\ &=4/3+o(1) \end{aligned} where we applied Stirling and the approximation $$e^{-n}\sum_{k=0}^n\frac{n^k}{k!}=\frac{\Gamma(n,n)+e^{-n}n^{n-1}}{(n-1)!} =\frac{e^{-n}n^{n}}{n!}\left(\sqrt{\frac{n\pi}{2}}-\frac{1}{3}+o(1)+1\right).$$ The asymptotics of the upper incomplete gamma function $\Gamma(n,n)$ is given here: NIST Digital Library of Mathematical Functions. See also Asymptotics for incomplete $\Gamma$ with equal arguments for a detailed proof.

Answer 3

There is a nice solution by @Robert Z, which uses the asymptotics of incomplete Gamma-function. We can also find the limit in a bit different way. Let's consider $$S(n)=\frac{n!}{n^n}\left(\sum_{k=0}^n\frac{n^k}{k!}-\sum_{k=n+1}^\infty \frac{n^k}{k!}\right)=\frac{n!}{n^n}\Big(e^n-2\sum_{k=n+1}^\infty \frac{n^k}{k!}\Big)=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-2e^{-n}\sum_{k=n+1}^\infty \frac{n^k}{k!}\Big)$$ Changing the order of summation $$=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-2e^{-n}\sum_{k=1}^\infty \frac{n^{k+n}}{(k+n)!}\Big)=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2n^ne^{-n}}{n!}\sum_{k=1}^\infty \frac{n^k}{k!}\frac{n!\,k!}{(k+n)!}\Big)$$ Using $\frac{n!\,k!}{(k+n)!}=\frac{n\Gamma(n)\Gamma(k+1)}{\Gamma(k+n+1)}=n\int_0^1t^{n-1}(1-t)^kdt$ $$S(n)=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}\sum_{k=1}^\infty \frac{n^k}{k!}\int_0^1n\,t^{n-1}(1-t)^kdt\Big)$$ Changing the order of summation and integration $$=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}\int_0^1n\,t^{n-1}dt\sum_{k=1}^\infty \frac{n^k}{k!}(1-t)^kdt\Big)$$ $$=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}\int_0^1n\,t^{n-1}\big( e^{n(1-t)}-1\big)dt\Big)$$ Integrating by part $$=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}\int_0^1n\,t^n e^{n(1-t)}dt\Big)=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}n\int_0^1 e^{n(1-t)+n\ln t}dt\Big)$$ Now we can use the Laplace method to find as many terms of the asymptotics as we want. Basically, we need only to keep the second term to find the limit.

$\,f(t)=1-t+\ln t\,$ has a maximum at $\,t=1$ $$ f'(t)=-1+\frac{1}{t}; \,f''(t)=-\frac{1}{t^2}; \,f'''(t)=\frac{2}{t^3}$$ $$f(t)=f(1)+\frac{1}{2}f''(1)(t-1)^2+\frac{1}{6}f'''(1)(t-1)^3+...=0-\frac{(t-1)^2}{2}+\frac{(t-1)^3}{3}+...$$ $$S(n)=\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}n\int_0^1 e^{-n\frac{(t-1)^2}{2}+n\frac{(t-1)^3}{3}+...}\,dt\Big)$$ As usual, with the accuracy up to exponentially small terms we extend integration to $-\infty$. Also, decomposing the exponent $e^{n\frac{(t-1)^3}{3}}=1+n\frac{(t-1)^3}{3}+...$ $$S(n)\sim\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}n\int_{-\infty}^0 e^{-n\frac{s^2}{2}+n\frac{s^3}{3}+...}\,ds\Big)$$ $$\sim\frac{n!}{\big(\frac{n}{e}\big)^n}\Big(1-\frac{2\big(\frac{n}{e}\big)^n}{n!}n\int_{-\infty}^0 e^{-n\frac{s^2}{2}}\big(1+n\frac{s^3}{3}+...\big)\,ds\Big)$$ Now, using the asymptotics of $n!=\sqrt{2\pi n}\big(\frac{n}{e}\big)^n \Big(1+O\big(\frac{1}{n}\big)\Big)$ $$S(n)=\sqrt{2\pi n}\bigg(1-\frac{2n}{\sqrt{2\pi n}}\Big(\int_0^\infty e^{-n\frac{s^2}{2}}ds-\frac{n}{3}\int_0^\infty e^{-n\frac{s^2}{2}}s^3\,ds+o\big(\frac{1}{n}\big)\Big)\bigg)$$ Integration is straightforward. $$S(n)=\sqrt{2\pi n}\Big(1-\frac{2n}{\sqrt{2\pi n}}\Big(\frac{\sqrt{2\pi}}{2\sqrt n}-\frac{2}{3n}+o\big(\frac{1}{n}\big)\Big)\Big)=\frac{4}{3}+o(1)$$