Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$ 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:


*

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

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

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

*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.
 A: 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
[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).
A: 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.$$ 
A: 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?
