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.



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


