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

Question

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

Answer 1

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