I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. 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{2k+1}{j}E^j$;

  2. These satisfy the inhomogeneous recurrence $P_k(E)-(1-E)^2P_{k-1}(E) =$ some binomial in $E$;

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

  4. Try to derive a recurrence for $P_k(E)x^{(2k-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 by clue 4.

  • $\begingroup$ Nitpicking: you need $k\geq 2$. $\endgroup$ Jun 22, 2010 at 17:54
  • $\begingroup$ 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 ;-) $\endgroup$ Jun 23, 2010 at 0:53
  • $\begingroup$ Thanks Pietro and Victor for the great answers. Hopefully this also will help ME. $\endgroup$ Jun 23, 2010 at 10:26
  • $\begingroup$ Thank you, everyone, for the beautiful answers. I am most grateful. $\endgroup$ Jun 25, 2010 at 3:26

3 Answers 3


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.



[edit]: 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).

  • $\begingroup$ I didn't expect that the original sequence is so easily expressed thru the Eulerian numbers. A very nice and elementary solution! +1 $\endgroup$ Jun 23, 2010 at 6:52
  • $\begingroup$ 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. $\endgroup$ Jun 23, 2010 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.$$


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

  • $\begingroup$ 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. $\endgroup$ Jun 22, 2010 at 21:32
  • $\begingroup$ 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). $\endgroup$ Jun 22, 2010 at 21:39
  • $\begingroup$ 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)$. $\endgroup$ Jun 25, 2010 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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