Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
Would you like to give us some background and motivation, as per mathoverflow.net/howtoask... –  David Roberts Jun 7 '13 at 3:55
3  
@Andres: I think the solution at SE is incorrect. –  GH from MO Jun 7 '13 at 5:13
9  
@domotorp Why don’t you think it is research level? He did some research and got stuck at some ugly inequality. Not everybody is like Ramanujan and the inequality is definitely non-trivial. –  The User Jun 7 '13 at 14:47
9  
I cast the final vote to reopen. The question is well-posed, not hopeless, and I cannot do it in 10 minutes, so, I guess, it can stay if not based on definitions, then based on precedents. –  fedja Jun 7 '13 at 17:00
4  
I just slogged through the Stirling's formula, Euler-Maclaurin approach and I got that the sum is $e^d (1-1/d+O(1/d^2)$ (in other words, inconclusive), after a ton of cancellation which required, among other things, knowing the $1/(12 n)$ term in Stirling's formula. I take this as evidence that this inequality is very tight, and probably not easy to prove by. –  David Speyer Jun 7 '13 at 17:17

3 Answers 3

up vote 44 down vote accepted

[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

share|improve this answer
    
Wow. Very impressive. –  Deane Yang Jun 8 '13 at 21:04
2  
++++1: wow! as usual, it is a pleasure to see Noam's solutions! –  Suvrit Jun 8 '13 at 22:33
    
Thanks Noam! Your answer is really helpful! –  useag Jun 9 '13 at 0:19
1  
This is a very slick trick. In the penultimate displayed equation, I think some $k$'s and $d$'s are switched (you want to sum on $k$, yes?) –  David Speyer Jun 10 '13 at 13:27
1  
Thanks to all! David Speyer is right; I've now edited my answer to fix that error. –  Noam D. Elkies Jun 23 '13 at 23:58

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.

share|improve this answer
    
Maybe we could try to prove that if the inequality holds true for a given large $d$, it still holds true for $d-1$? This would settle the problem for all $d$. –  Sylvain JULIEN Jun 7 '13 at 21:39
    
I also thank you very much for your answer –  useag Jun 9 '13 at 0:22

[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.]

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.