the following inequality is true, but I can't prove it

Question

The inequality $$\sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right)$$ holds for all integer $d\geq 1$. I use computer to verify it for $d\leq 50$, and find it is true, but I can't prove it. Thanks for your answer.

Answer 1

This is only a hint, not an answer.

Denote your sum by $s(d)$ and let $g(d):=e^d\> s(d)-\bigl(1-{1\over d}\bigr)$. Looking at a list plot of $g$ for $1\leq d\leq 200$ one can see that the conjectured inequality becomes sharper (and not more obvious) with increasing $d$. This suggests that for a proof one would have to start at $d=\infty$.

Answer 2

This is a report of a failed attempt. I tried to do this in the standard brute force way, as described in books like Concrete Mathematics. What I wound up proving is that the sum is $$e^d (1-O(1/d) + O(d^{-3/2+\epsilon}))$$ for any $\epsilon$. In other words, I failed to answer the question. If I needed this result for a paper, and I didn't have a better idea, I would go through again keeping all terms up to $O(d^{-5/2+\epsilon})$ But, as I don't need it, I leave that to you.

UPDATE I found a slicker way to do this, and wrote it up over on MO. The result is that the sum is $$e^d(1-1/d+1/d^2+ O(d^{-2.5+\epsilon}).$$ I still don't have a proof for all $d$.

Cutting off the tails: Put $k = d+\ell$. The first thing I want to point out is that terms with $|\ell| > d^{0.5+\epsilon}$ are negligible. Proof sketch: Suppose that $\ell > d^{0.5+\epsilon}$. Then $$\frac{d^k}{k!} = \frac{d^d}{d!} \frac{d^{\ell}}{(d+1)(d+2)\cdots (d+\ell)} \leq \frac{d^d}{d!} \prod_{i=1}^{\ell} e^{-i/d} = \frac{d^d}{d!} e^{-(\ell^2+\ell)/d}.$$ For $\ell> d^{0.5+\epsilon}$, that exponent is $\geq d^{2 \epsilon}$, and hence the contribution from these terms is $e^{-d^{2 \epsilon}}$ smaller than the contribution of the central term. A similar argument works when $\ell < - d^{0.5+\epsilon}$. So we will concentrate on the range $-d^{0.5+\epsilon} < \ell < d^{0.5-\epsilon}$.

Asymptotic analysis of the summand: As before, write the summand as $$\frac{d^d}{d!} \frac{1}{\prod_{i=1}^{\ell} (1+i/d)} \left( 1- \frac{1}{d+2-\ell} \right).$$ We now analyze that product much more carefully. $$ \frac{1}{\prod_{i=1}^{\ell} (1+i/d)} = \exp \left(- \sum_{i=1}^{\ell} \log \left( 1+\frac{i}{d} \right) \right)$$ $$ = \exp \left(-\frac{1}{d} \sum_{i=1}^{\ell} i + \frac{1}{2 d^2} \sum_{i=1}^{\ell} - \frac{1}{3d^3} \sum_{i=1}^{\ell} i^3 + O(\ell^5/d^4) \right) $$ $$=\exp\left( -\ell^2/(2d) + [ - \ell/(2d)+\ell^3/(6 d^2) ] + [ \ell^2/(4 d^2)- (\ell^4)(12 d^3)] + O(d^{-3/2+0.03}) \right)$$ $$=e^{-\ell^2/(2d)} \left( 1+ [-\ell/(2d) +\ell^3/(6 d^2)] + [3 \ell^2/(8 d^2) -\ell^4/(6 d^3)+ \ell^6/(72 d^4)] + O(d^{-3/2+3 \epsilon}) \right).$$ The terms in square brackets are of the same magnitude when $\ell \approx \sqrt{d}$.

Meanwhile, by Striling's approximation, $$\frac{d^d}{d!} = \frac{e^d}{\sqrt{2 \pi d}} (1-1/(12 d) + O(1/d^2))$$ and $$\left( 1- \frac{1}{d+2-\ell} \right) = 1-1/d + O(\ell/d^2).$$

Putting it all together $$\frac{e^d}{\sqrt{2 \pi d}} \sum_{\ell = -d^{0.51}}^{d^{0.51}} e^{-\ell^2/d} \times \left( 1+ [-\ell/(2d) +\ell^3/(6 d^2)] + [-(13)/(12 d) + 3 \ell^2/(8 d^2) -\ell^4/(6 d^3)+ \ell^6/(72 d^4)] + O(d^{-3/2+3 \epsilon}) \right).$$

Replacing the sum by an integral We replace the sum on $\ell$ by the corresponding integral. The error in doing so is given by the Euler-Maclaurin formula. I'm too lazy to work it out but, since the summand is smooth and is exponentially small at the endpoints, this should be negligible compared to the errors we already have. We then substitute $x = \ell/\sqrt{d}$. This cancels the $\sqrt{d}$ outside the integral and leaves: $$\frac{e^d}{\sqrt{2 \pi}} \int_{x = -d^{\epsilon}}^{d^{\epsilon}} e^{-x^2} dx \times \left( 1+ \frac{1}{\sqrt{d}} [-x/2 +x^3/3] + \frac{1}{d} [-13/12 + 3 x^2/8 -x^4/6+ x^6/72] + O(d^{-3/2+3 \epsilon}) \right).$$

Conveniently, the integrand in the coefficient of $1/\sqrt{d}$ is odd and hence vanishes. Also, we can replace the integration bound by $-\infty$ and $\infty$ with exponentially small error. But now a crazy miracle happens! According to Mathematica, $$\frac{1}{\sqrt{2 pi}} \int_{x=infty}^{-\infty} (-13/12 + 3 x^2/8 -x^4/6+ x^6/72) dx=-1.$$ In other words, the $1/d$ term is exactly what you expect on the right hand side.

We could redo this computation keeping track of more error terms. The integrand in from of $1/d^{3/2}$ is odd again. I didn't have the energy to go on to $1/d^2$.

UPDATE Following an idea of Christian Blatter, I plotted $$\left( \log d, \log \left( e^{-d} \sum_{k=1}^{2d} \frac{d^k}{k!} - 1+1/d \right) \right)$$ for $d$ from $5$ to $50$.

It looks linear, with slope $-2$. A best fit line is $-1.8 \log d - 0.8$. So I predict there is a nontrivial $d^{-2}$ term.

Answer 3

Sorry I didn't check this sooner: the problem was cross-posted at mathoverflow and I eventually was able to give a version of David Speyer's analysis that makes it feasible to compute many more coefficient of the asymptotic expansion (I reached the $d^{-13}$ term, and could go further), and later to give error bounds good enough to prove the inequality for $d \geq 14$, at which point the previous numerical computations complete the proof. See https://mathoverflow.net/questions/133028/the-following-inequality-is-truebut-i-cant-prove-it/133123#133123