Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T06:14:02Z http://mathoverflow.net/feeds/question/29118 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29118/need-help-proving-that-sum-limits-j0k-1-1j1k-j2k-2-binom2k1 Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ Alexandra Seceleanu 2010-06-22T16:51:33Z 2010-06-23T15:28:10Z <p>Hello. </p> <p>I have been trying very hard to show that <code>$\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$</code> and could not quite get anywhere. This inequality has been verified by computer for <code>$k\le40$</code>.</p> <p>Some clues that might work (kindly provided by Doron Zeilberger) are as follows:</p> <ol> <li><p>Let $Ef(x):=f(x-1)$, let <code>$P_k(E):=\sum_{j=0}^{k-1}(-1)^{(j+1)}*\binom{2*k+1}{j}*E^j$</code>;</p></li> <li><p>These satisfy the inhomogeneous recurrence <code>$P_k(E)-(1-E)^2*P_{k-1}(E)=Some Binomial In E$</code>;</p></li> <li><p>The original sum can be expressed as <code>$P_k(E)x^{(2*k-2)} | x=k$</code>;</p></li> <li><p>Try to derive a recurrence for <code>$P_k(E)x^{(2*k-2)}$</code> before plugging-in $x=k$ and somehow use induction, possibly having to prove a more general statement to facilitate the induction.</p></li> </ol> <p>Unfortunately I do not know how to find a recurrence such as suggested in 4.</p> <p>I would appreciate any help that members of the MathOverflow community can provide.</p> http://mathoverflow.net/questions/29118/need-help-proving-that-sum-limits-j0k-1-1j1k-j2k-2-binom2k1/29148#29148 Answer by David Carchedi for Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ David Carchedi 2010-06-22T21:29:31Z 2010-06-22T21:29:31Z <p>I believe it has to do with the following:</p> <p>Let $P(x)$ be an arbitary polynomial of of degree less than or equal to $n$ such that $P(X) \in \mathbb{Z}$ for all $x \in \mathbb{Z}$. Then $P(x)$ can be expressed uniquely as an integer combination of binomial coefficients of the form <code>$\left({\begin{array}{*{20}c} {x + j} \\ n \\\end{array}}\right)$</code>, that is:</p> <p><code>$$P(x) = \sum\limits_{j = 0}^{n - 1} {a_{n - j} \left( {\begin{array}{*{20}c} {x + j} \\ n \\ \end{array}} \right)}$$</code></p> <p>(assuming $x \in \mathbb{Z}$). Specifically, we have:</p> <p><code>$$a_j = \sum\limits_{l = 0}^j {\left( { - 1} \right)^l P(j - l)\left( {\begin{array}{*{20}c} {n + 1} \\ l \\ \end{array}} \right).}$$</code></p> <p>Now let $n=2k$ and expand out $\left(x+1\right)^{2k-2}$ in terms of the binomial coefficients <code>$\left({\begin{array}{*{20}c} {x + j} \\ 2k \\\end{array}}\right)$</code>:</p> <p><code>$$(x + 1)^{2k - 2} = \sum\limits_{j = 0}^{2k - 1} {a_{n - j}^i \left( {\begin{array}{*{20}c} {x + j} \\ {2k} \\ \end{array}} \right)}.$$</code></p> <p>Then we have that</p> <p><code>$$a_{k-1} = \sum\limits_{j = 0}^{k-1} {\left( { - 1} \right)^j \left(k-j\right)^{2k-2}\left( {\begin{array}{*{20}c} {2k + 1} \\ j \\ \end{array}} \right).}$$</code></p> <p>This is exactly the negative of your coefficient. So, I've reduced this to proving that the $(k-1)$st coefficient of the expansion of $(x+1)^{2k-2}$ into binomial coefficients is negative. I hope this helps. If you figure this out, please let me know. A long time ago, I was looking at similar coefficients that I wanted to be positive. (Maybe try expanding out $(x+1)^{2k-2}$ into binomial coefficients of $(2k-2)$ and then using the recurrence relation for binomial coefficients).</p> <p>P.S. Where is this expression coming from, in your case?</p> http://mathoverflow.net/questions/29118/need-help-proving-that-sum-limits-j0k-1-1j1k-j2k-2-binom2k1/29179#29179 Answer by Pietro Majer for Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ Pietro Majer 2010-06-23T00:27:48Z 2010-06-23T15:28:10Z <p>Your expression is the difference of two central Eulerian numbers , </p> <p>$$A(k):=\sum_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2}{2k+1 \choose j}=\left \langle {2k-2\atop k-2} \right \rangle-\left \langle {2k-2\atop k-3} \right \rangle$$</p> <p>as you can easily deduce from their closed formula. The positivity of $A(k)$ is just due to the fact that the Eulerian numbers $\left \langle {n\atop j}\right \rangle$ are increasing for $1\leq j\leq n/2$ (like the binomial coefficients); this fact has a clear combinatorial explanation also. </p> <p>See e.g.</p> <p><a href="http://en.wikipedia.org/wiki/Eulerian_number" rel="nofollow">http://en.wikipedia.org/wiki/Eulerian_number</a></p> <p><a href="http://www.research.att.com/~njas/sequences/A008292" rel="nofollow">http://www.research.att.com/~njas/sequences/A008292</a></p> <p><strong></strong>: although by now all details have been very clearly explained by Victor Protsak, I wish to add a general remark, should you find yourself in an analogous situation again. A healthy approach in such cases is adding variables, following the motto "more variables = simpler dependence" (like when one passes from quadratic to bilinear). In the present case, you may consider</p> <p>$$A(k):=a(k,\, 2k-2,\,2k+1)$$</p> <p>where you define</p> <p>$$a(k,n,m):=\sum_{j=0}^{k-1}(-1)^{j+1}(k-j)^{n}{m \choose j}$$</p> <p>in which it is more apparent the action of the iterated difference operator, or, in the formalism of generating series, the Cauchy product structure:</p> <p>$$\sum_{k=0}^\infty a(k,n,m)x^k=-\sum_{j=0}^\infty j^nx^j\ \sum_{j=0}^\infty(-1)^j{m \choose j} x^j =-(1-x)^m\sum_{j=0}^\infty j^nx^j.$$</p> <p>The series $$\sum_{j=0}^\infty j^nx^j$$ is now quite a simpler object to investigate, and in fact it is well-known to whoever played with power series in childhood. It sums to a rational function<br> $$(1-x)^{-n-1}x\sum_{k=0}^{n}\left \langle {n\atop k}\right \rangle x^k$$ that defines the Eulerian polynomial of order $n$ as numerator, and the Eulerian numbers as coefficients. In your case, m=n+3, meaning that you are still applying a discrete difference twice (in fact just once, due to the symmetric relations; check Victor's answer).</p> http://mathoverflow.net/questions/29118/need-help-proving-that-sum-limits-j0k-1-1j1k-j2k-2-binom2k1/29198#29198 Answer by Victor Protsak for Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ Victor Protsak 2010-06-23T07:30:15Z 2010-06-23T07:30:15Z <p><em>This is a clarification of Pietro Majer's beautiful and insightful, yet a bit cryptic answer.</em></p> <p>The <a href="http://en.wikipedia.org/wiki/Eulerian_numbers" rel="nofollow">Eulerian numbers</a> are expressible as </p> <p>$$\left\langle {n\atop m}\right\rangle=\sum_{i=0}^m(-1)^i{n+1\choose i}(m+1-i)^n.$$</p> <p>View them as functions of $m$ and let $\Delta$ be the backward difference operator, </p> <p>$$\Delta f(m)=f(m)-f(m-1).$$</p> <p><b>Claim </b> The $r$th iterated backward difference of the Eulerian number is given by the formula</p> <p>$$\Delta^r\left\langle {n\atop m}\right\rangle=\sum_{i=0}^m(-1)^i{n+r+1\choose i}(m+1-i)^n.$$</p> <p><b>Proof</b> This is proved by induction in $r$ using the binomial identity $${n+r\choose i}+{n+r\choose i-1}={n+r+1\choose i}. \quad\square$$</p> <p>Setting $m=k-1$ and comparing with the definition of the sequence, we see that </p> <p>$$A(k)=\sum_{j=0}^{k-1}(-1)^{j+1}{2k+1 \choose j}(k-j)^{2k-2}=-\Delta^2\left\langle {n\atop k-1}\right\rangle\ \text{evaluated at }\ n=2k-2.$$</p> <p>Thus </p> <p>$$A(k) = -\Delta\left\langle {n\atop k-1}\right\rangle + \Delta\left\langle {n\atop k-2}\right\rangle = \Delta\left\langle {n\atop k-2}\right\rangle\ \text{evaluated at }\ n=2k-2$$</p> <p>and the first summand vanishes due to the symmetry of the Eulerian numbers, $\left\langle {n\atop m}\right\rangle=\left\langle {n\atop n-1-m}\right\rangle$, which implies that $\left\langle {2k-2\atop k-1}\right\rangle=\left\langle {2k-2\atop k-2}\right\rangle.$ </p> <p>Now the positivity of $A(k)$ becomes a consequence of the unimodality of the Eulerian numbers, $\Delta\left\langle {n\atop m}\right\rangle\geq 0$ for $m\leq n/2.$ Explicitly, $$A(k)=\left\langle {2k-2\atop k-2}\right\rangle-\left\langle {2k-2\atop k-3}\right\rangle > 0\ \text{for}\ k\geq 2.$$ </p>