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

Question

The inequality is \begin{equation*} \sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right) \end{equation*} 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

[Edited mostly to fix a typo noted by David Speyer]

The following analysis simplifies and completes the "routine but somewhat unpleasant" task of recovering the actual inequality from the asymptotic analysis.

The idea is that once we've obtained the asymptotic expansion $$ \sum_{k=1}^{2d} \left( 1 - \frac1{2d+2-k} \right) \frac{d^k}{k!} \sim e^d \left( 1 - \frac1{d} + \frac1{d^2} - \frac2{d^3} \cdots \right) $$ by expanding $1 - 1/(2d+2-k)$ in a power series about $k=d$, we should be able to replace $1 - 1/(2d+2-k)$ by something smaller that can be summed exactly and is close enough that the result is within a small enough multiple of $e^d$ to maintain the desired inequality.

Because it takes about $2m$ terms of the power series in $k$ to get within $O(1/d^m)$, I had to match the power series to within $O(k-d)^6$. Let $$ A_6(k) = \frac{d+1}{d+2} - \frac{k-d}{(d+2)^2} - \frac{(k-d)^2}{(d+2)^3} - \frac{(k-d)^3}{(d+2)^4} - \frac{(k-d)^4}{(d+2)^5} - \frac{(k-d)^5}{(d+2)^6} - \frac{(k-d)^6}{2(d+2)^6}, $$ so the final term has denominator $2(d+2)^6$ instead of $(d+2)^7$. Then $$ 1 - \frac1{2d+2-k} = A_6(k) + \frac{(k-d)^6(2d-k)}{2(d+2)^6(2d+2-k)} \geq A_6(k) $$ for all $k \leq 2d$. Hence $$ \sum_{k=1}^{2d} \left( 1 - \frac1{2d+2-k} \right) \frac{d^k}{k!} > \sum_{k=1}^{2d} A_6(k) \frac{d^k}{k!}. $$ On the other hand, since $A_6(k)$ is a polynomial in $k$, the power series $\sum_{k=0}^\infty A_6(k) d^k/k!$ is elementary (see my earlier answer for the explanation; David Speyer implicitly used this too in the calculation "with the aid of Mathematica"). I find $$ \sum_{k=0}^\infty A_6(k) \frac{d^k}{k!} = \frac{2d^6 + 22d^5 + 98d^4 + 102d^3 + 229d^2 + 193d + 64}{2(d+2)^6} e^d $$ $$ = \left( 1 - \frac1d + \frac{2d^5 + 5d^4 + 69d^3 + 289d^2 + 320d + 128}{2d(d+2)^6} \right) \cdot e^d > \left(1 - \frac1d\right) e^d. $$ We're not quite finished, because we need a lower bound on $\sum_{k=1}^{2d} A_6(k) d^k/k!$, not $\sum_{k=0}^\infty$. However, once $d$ is at all large the terms with $k=0$ and $k>2d$ are negligible compared with our lower bound $$ \sum_{k=0}^\infty A_6(k) d^k/k! - \left(1 - \frac1d\right) e^d \geq \frac{2d^5 + 5d^4 + 69d^3 + 289d^2 + 320d + 128}{2d(d+2)^6} e^d > \frac{d^4}{(d+2)^6} e^d. $$ Indeed the $k=0$ term is less than $1$, and for $k>2d$ we have $A_6(k) < A_6(2d) = 1/2$ while $d^k/k!$ is exponentially smaller than $e^d$: $$ \sum_{k=2d+1}^\infty \frac{d^k}{k!} < 2^{-2d} \sum_{k=2d+1}^\infty \frac{(2d)^k}{k!} < 2^{-2d} \sum_{k=0}^\infty \frac{(2d)^k}{k!} = (e/2)^{2d}. $$ So we're done once $$ 1 + \frac12 \left(\frac{e}{2}\right)^{2d} < \frac{d^4}{(d+2)^6} e^d, $$ which happens once $d \geq 14$. Since the desired inequality has already been verified numerically up to $d=50$, we're done. QED

Answer 2

This is true for large $d$, and probably for all $d$. I'll prove that the sum is $$e^d(1-1/d+1/d^2+O(1/d^{2.5+\epsilon}))$$ and leave the explicit bounds to you.

Set $k=d+\ell$. For $|\ell| \leq d^{0.5+\epsilon}$, we have $$1-1/(2d+2-k) = 1-\frac{1}{d} \frac{1}{1-(\ell-2)/d} = 1-\frac{1}{d} - \frac{\ell-2}{d^2} - \frac{(\ell-2)^2}{d^3} + O(d^{-2.5+3 \epsilon})$$ $$=1-\frac{1}{d} - \frac{\ell}{d^2} + \frac{2 d - \ell^2}{d^3} + O(d^{-2.5+\epsilon}).$$

We will show later that the difference between your sum and $$\sum_{k=0}^{\infty} \frac{d^k}{k!} \left( 1-\frac{1}{d} - \frac{\ell}{d^2} + \frac{2 d - \ell^2}{d^3} \right)$$ is very small, where $\ell = k-d$. Assuming that, let's compute the new sum. With the aid of Mathematica, $$\sum_{k=0}^{\infty} \frac{x^k}{k!} \left( 1-\frac{1}{d} - \frac{k-d}{d^2} + \frac{2 d - (k-d)^2}{d^3} \right) = e^x \left( 1-\frac{1}{d}+\frac{x}{d^2}-\frac{x^2}{d^3} + \frac{2}{d^2} - \frac{x}{d^3} \right). $$

Plugging in $x=d$, $$\sum_{k=0}^{\infty} \frac{d^k}{k!} \left( 1-\frac{1}{d} - \frac{k-d}{d^2} + \frac{2 d - (k-d)^2}{d^3} \right) = e^d \left( 1-\frac{1}{d} + \frac{1}{d^2} \right).$$ The error coming from $O(d^{-2.5+\epsilon}) \sum d^k/k!$ is $e^d O(d^{-2.5+\epsilon})$.

We now just need to think about the error coming from discarding the terms with $|\ell|>d^{0.5+\epsilon}$. No matter what $\ell$ is, that error is no worse than $d^k/k! \cdot ( O(\ell^2/d^3) + O(1))$. But, for $|\ell| > d^{0.5 + \epsilon}$, we have $d^k/k! \leq e^{-d^{2 \epsilon}}$ as I pointed out on math.SE, so the contribution from these terms is exponentially small.

I have not found a slick way to give a proof for all $d$, rather than an asymptotic result.

Answer 3

[I think the following comes down to basically what David Speyer is doing, systematized to get as much of the asymptotic expansion as we want.]

For large $d$ there's an asymptotic expansion $$ \sum_{k=1}^{2d} \left( 1 - \frac1{2d+2-k} \right) \frac{d^k}{k!} = e^d \left( 1 - \frac1d + \frac1{d^2} - \frac2{d^3} - \frac4{d^4} - \frac{52}{d^5} - \frac{608}{d^6} \cdots \right)\phantom.. $$ It should be routine but somewhat unpleasant to get error estimates for the expansion through $1/d^2$ sufficient to prove the desired inequality for all $d$ (given that it is known to be true up to $d=50$ by numerical computation).

To obtain $m$ terms of this asymptotic expansion, we need about $2m$ terms of the Taylor expansion of $1 - 1/(2d+2-k)$ about $k=d$, which is the peak of $d^k/k!$. This Taylor expansion is a constant minus a geometric series: $$ 1 - \frac1{2d+2-k} = \frac{d+1}{d+2} - \frac{k-d}{(d+2)^2} - \frac{(k-d)^2}{(d+2)^3} - \frac{(k-d)^3}{(d+2)^4} - \cdots . $$ Now when we truncate this expansion before the $O((k-d)^N)$ term we get $(d+2)^{-N}$ times a polynomial in $d$ and $k$. We can then write that polynomial as a finite sum $$ P_0(d) + k P_1(d) + k(k-1) P_2(d) + k(k-1)(k-2) P_3(d) + \cdots $$ and then multiplying each term $k! P_i(d) / (k-i)!$ by $d^k/k!$ and summing over $k \geq 0$ we get $P_i(d) d^i e^d$. Hence our $N$-th approximation is $\sum_i P_i(d) d^i e^d \left/ (d+2)^N \right.$, which is $e^d$ times some rational function in $d$. Expanding this rational function about $d = \infty$ we obtain the above power series once $N \geq 11$.

[The next few coefficients past $-608$ are $$ -8864, -151408, -1973184, -65998976, -1633489408, -44681812096, -1336497292288; $$ no, this sequence is not in the OEIS.]