How to prove $\frac{n^n}{3n!}<\frac{e^n}{2}-\sum_{k=0}^{n-1}\frac{n^k}{k!}<\frac{n^n}{2n!}$ I met this problem:
prove:
$\displaystyle \frac{n^n}{3n!}<\frac{e^n}{2}-\sum_{k=0}^{n-1}\frac{n^k}{k!}<\frac{n^n}{2n!}$
I tried expand $e^n$ at $x=0$ then:
$\displaystyle e^n=\sum_{k=0}^{n}\frac{n^k}{k!}+\frac1{n!}\int_0^ne^t(n-t)^ndt$
but I have no idea next...
And another way of thinking:both side divided $e^n$ the LHS became $\displaystyle \frac{n^n}{3n!e^n}$ then can we use the stirling's fomula to find sth.?
Could someone help me? Thanks!
 A: A re-worked answer. We have:
$$ e^n = \sum_{k=0}^{n}\frac{n^k}{k!}+\frac{n^{n+1}}{n!}\int_{0}^{1}\left(e^t(1-t)\right)^n\,dt\tag{1}$$
but we also have:
$$\forall x\in[0,1],\qquad (1-x^3)e^{-x^2/2} \leq e^{x}(1-x) \leq e^{-x^2/2}\tag{2}$$
hence:
$$ \int_{0}^{1}\left(e^t(1-t)\right)^n\,dt \leq \int_{0}^{+\infty}e^{-nx^2/2}\,dx =  \sqrt{\frac{\pi}{2n}}\tag{3}$$
and for every $n\geq 11$:
$$\begin{align*} \int_{0}^{1}\left(e^t(1-t)\right)^n\,dt \geq \int_{0}^{1}(1-t^3)^n e^{-nt^2/2}\,dt &\geq \int_{0}^{1}(1-nt^3) e^{-nt^2/2}\,dt\\&\geq \int_{0}^{1}e^{-nt^2/2}\,dt-\frac{2}{n}\\&\geq \sqrt{\frac{\pi}{2n}}-\frac{4}{n}.\end{align*}\tag{4}$$
We may go through these lines, improving a bit $(3)$ and $(4)$, or use some probabilistic argument, since we are essentially estimating the probability that a Poisson distributed random variable exceeds its mean value.
A: I only got asymptotic inequality. Numerical exploration tells us that the quantity in question - properly rescaled monotonically approaches the left limit in the inequality.
Asymptotics. After expanding $e^n=\sum_{k=0}^{n}\frac{n^k}{k!}+\frac1{n!}\int_0^ne^t(n-t)^ndt$, making a substitution $t=nx$ in the integral and rearranging the terms, the original inequality becomes
$$-\frac{2}{3}<\big(\int_{0}^{1}(e^t(1-t))^ndt -{\frac{K(n)}{2n}}\big)n < -\frac{1}{2}\tag{1}$$
where $K(n)=\displaystyle\frac{n!e^n}{n^n}=\sqrt{2\pi n}(1+\frac 1 {12n}+O(\frac 1 {n^2})\big)\tag{2}$
Use Laplace method to evaluate $\displaystyle I(n)=\int_{0}^{1}\big(e^t(1-t))^ndt=\int_0^1e^{nh(t)}dt$
where $$h(t)=t+\log(1-t)$$
$h$ achieves its maximum at $t=0$ and takes on values $h(0)=0, h'(0)=0,h^{(i)}(0)=-(i-1)!=h_i$ for $i\geq 2$. Expand $h(x)=h_0+\sum_{i\geq 2}h_ix^i/i!$ to get 
Applying Laplace's method we get
$$I(n)=e^{nh_0}\Big(\frac 1 2\frac {\sqrt{2\pi \sigma}} {n^{1/2}}+\frac {h_3\sigma^2}{3n}+\frac{\sqrt{2\pi \sigma}}{n^{3/2}}\big(\frac{h_4\sigma^2}{16}+\frac{5h_3^2\sigma^3}{48}\big)+\big({h_3h_4\sigma^4\over 3}+{8h_5\sigma^3 \over 5}\big)\frac {1} {n^2}+O(\frac 1 {n^{5/2}})\Big)=\frac{\sqrt{2\pi}}{2n^{1/2}}-\frac 2 {3n}+\frac {\sqrt{2\pi}} {24n^{3/2}}+{12\over 5n^2}+O(\frac 1 {n^3})\tag{3}$$
where $\sigma=|1/h_2|$. Note that in our case the the maximum is achieved at the boundary, hence compared to the case when maximum is achieved in the middle we get a factor of $1/2$ in from of even powers of $x$ in Taylor the expansion before integration and odd powers of $x$ aren't cancelled out.
Plug $(3)$ into (1) using (2) to get $$-\frac 2 3<-\frac 2 3+{12\over 5n}+O(\frac 1 {n^2})<-\frac 1 2$$ which holds.
For small $n$, values of $G(n)=\big(I(n)-\frac{K(n)}{2n}\big)n$ are $G(1)=e/2-2\approx -0.64,
G(2)=1/(e^2-10)\approx -0.65274, 
G(3)=1/9(e^3-26)\approx -0.65716$
so it looks like the G(n) is monotonically decreasing to $-2/3$ which we know happens asymptotically and is already very close.
Can you prove inequality for all $n$?
