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


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.

share|improve this question
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

3 Answers 3

up vote 31 down vote accepted

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

share|improve this 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.$$


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

share|improve this answer

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?

share|improve this answer
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

Your Answer


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.