3 edited body

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.research.att.com/~njas/sequences/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+2m=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).

2 added 1362 characters in body

$A(k):=\sum_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2}{2k+1$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$rangle$$: 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+2, meaning that you are still applying a discrete difference twice (in fact just once, due to the symmetric relations; check Victor's answer). 1 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.research.att.com/~njas/sequences/A008292