Need help proving that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$

Hello.

I have been trying very hard to show that $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$ and could not quite get anywhere. This inequality has been verified by computer for $k\le40$.

Some clues that might work (kindly provided by Doron Zeilberger) are as follows:

1. Let $Ef(x):=f(x-1)$, let $P_k(E):=\sum_{j=0}^{k-1}(-1)^{(j+1)}*\binom{2*k+1}{j}*E^j$;

2. These satisfy the inhomogeneous recurrence $P_k(E)-(1-E)^2*P_{k-1}(E)=Some Binomial In E$;

3. The original sum can be expressed as $P_k(E)x^{(2*k-2)} | x=k$;

4. Try to derive a recurrence for $P_k(E)x^{(2*k-2)}$ before plugging-in $x=k$ and somehow use induction, possibly having to prove a more general statement to facilitate the induction.

Unfortunately I do not know how to find a recurrence such as suggested in 4.

I would appreciate any help that members of the MathOverflow community can provide.

-
Nitpicking: you need $k\geq 2$. –  darij grinberg Jun 22 '10 at 17:54
Your sequence -1,1,10,245,11326,855162,.. is not contained in the Online Encyclopedia of Integer Sequences. If you find it interesting, as David Carchedi also suggests, you may like to include it ;-) –  Pietro Majer Jun 23 '10 at 0:53
Thanks Pietro and Victor for the great answers. Hopefully this also will help ME. –  David Carchedi Jun 23 '10 at 10:26
Thank you, everyone, for the beautiful answers. I am most grateful. –  Alexandra Seceleanu Jun 25 '10 at 3:26

Your expression is the difference of two central Eulerian numbers ,

$$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$$

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.

See e.g.

http://en.wikipedia.org/wiki/Eulerian_number

http://www.oeis.org/A008292

: 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

$$A(k):=a(k,\, , 2k-2,\, ,2k+1)$$

where you define

$$a(k,n,m):=\sum_{j=0}^{k-1}(-1)^{j+1}(k-j)^{n}{m \choose j}$$

in which it is more apparent the action of the iterated difference operator, or, in the formalism of generating series, the Cauchy product structure:

$$\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.$$

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
$$(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).

-
I didn't expect that the original sequence is so easily expressed thru the Eulerian numbers. A very nice and elementary solution! +1 –  Wadim Zudilin Jun 23 '10 at 6:52
That last series / rational function can also be expressed as $Li_{-n}(x)$, a polylogarithm of negative order. The equations for the generating series $-(1-x)^m Li_{-n}(x)$ are probably easy to get from MGfun, and are likely to be particularly simple. –  Jacques Carette Jun 23 '10 at 23:23

This is a clarification of Pietro Majer's beautiful and insightful, yet a bit cryptic answer.

The Eulerian numbers are expressible as

$$\left\langle {n\atop m}\right\rangle=\sum_{i=0}^m(-1)^i{n+1\choose i}(m+1-i)^n.$$

View them as functions of $m$ and let $\Delta$ be the backward difference operator,

$$\Delta f(m)=f(m)-f(m-1).$$

Claim The $r$th iterated backward difference of the Eulerian number is given by the formula

$$\Delta^r\left\langle {n\atop m}\right\rangle=\sum_{i=0}^m(-1)^i{n+r+1\choose i}(m+1-i)^n.$$

Proof 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$$

Setting $m=k-1$ and comparing with the definition of the sequence, we see that

$$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.$$

Thus

$$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$$

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.$

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.$$

-

I believe it has to do with the following:

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 $\left({\begin{array}{*{20}c} {x + j} \\ n \\\end{array}}\right)$, that is:

$$P(x) = \sum\limits_{j = 0}^{n - 1} {a_{n - j} \left( {\begin{array}{*{20}c} {x + j} \\ n \\ \end{array}} \right)}$$

(assuming $x \in \mathbb{Z}$). Specifically, we have:

$$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).}$$

Now let $n=2k$ and expand out $\left(x+1\right)^{2k-2}$ in terms of the binomial coefficients $\left({\begin{array}{*{20}c} {x + j} \\ 2k \\\end{array}}\right)$:

$$(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)}.$$

Then we have that

$$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).}$$

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.S. Where is this expression coming from, in your case?

-
P.S. in this case, since $2k-2 < 2k$, the sum of all the $a_j$s will be zero, in case this ends up helping. –  David Carchedi Jun 22 '10 at 21:32
P.P.S, it would appear that this in fact has to do with the dimension of the space of covariants of the regular representation of the symmetric group $S_{2k}$. If this rings a bell, we should talk (if not, maybe we should talk anyway). –  David Carchedi Jun 22 '10 at 21:39
In my case, these numbers appeared as follows: Consider the algebra $A_{r,t}=k[x_1,\ldots x_n]/(l_1^t,\ldots l_{r+1}^t)$ whose Hilbert function is given by $HF(A_{r,t},i)=\sum\limits_{j=0}^m(-1)^j\binom{r-1+i-tj}{r-1} \cdot \binom{r+1}{j}$ where $m=\mbox{min}\{\lfloor \frac{i}{t} \rfloor,r \}$. Now set $r=2k$. I am interested in the asymptotics of $HF(A_{r,t},k(t-1)-1)$. Turns out this is a polynomial in $t$ whose leading coefficient can be expressed (as I have just learned from the answers above) using Eulerian numbers as $\frac{1}{(2k-2)!}A(2k-2,k-2)$. –  Alexandra Seceleanu Jun 25 '10 at 3:51