Let $u(k,j) = 1$ if $j=0$, $0$ if $j > k$, or else it is $j\*u(k-1,j-1) +(j+1)\*u(k-1,j) $. Prove that $ \sum\_{i=0}^{2k} {n \choose i+1} u(2k,i) +\sum\_{i=0}^{2k} {-n-1 \choose i+1} u(2k,i)=0. $ This problem is provable using Bernoulli numbers but I'm interested if there's a proof that doesn't require the Bernoulli numbers. Any thoughts or ideas?


By the way it follows that $u(k,j) = \sum\_{i=0}^j {j\choose i}(-1)^i (j+1-i)^k$.



Show that $\sum_{i=0}^{2k} [ {n\choose i+1} + (-1)^{i+1}{n+i+1\choose i+1} ] \sum_{j=0}^i {i\choose j}(-1)^j (i+1-j)^{2k} =0.$
As pointed out by Ira Gessel, $u(k,j)=j!S(k+1,j+1)$. Correspondingly, the sum in question reduces to
$$f\_{2k}(n) + f\_{2k}(-n-1),$$
where
$$f\_k(t):=\sum\_{i=1}^{k+1} S(k+1,i)\frac{(t)\_i}i,$$
where $(t)\_i := t(t-1)\cdots(t-i+1)$ is the falling factorial.


Using the recurrence $S(k+1,i)=iS(k,i)+S(k,i-1)$, we get
$$f\_k(t)=\sum\_{i=1}^{k+1} S(k,i)(t)\_i + \sum\_{i=1}^{k+1} S(k,i-1)\frac{(t)\_i}{i} =t^{k} + \sum\_{i=1}^{k+1} S(k,i-1)\frac{(t)\_i}{i}.$$
Now, for a positive integer $t$, we have $\frac{(t)\_i}{i} = \sum\_{j=0}^{t-1} (j)\_{i-1}$, and thus
$$f\_k(t) = t^{k} + \sum\_{j=0}^{t-1} j^{k} = \sum\_{j=0}^t j^{k}.$$
Similarly, for a negative integer $t$, we get $f\_k(t) = (-1)^{k+1}\sum\_{j=0}^{-t-1} j^{k}$.


From the obtained formulae for $f\_k$ it follows that
$$f\_{2k}(n) + f\_{2k}(-n-1) = 0.$$


