How to prove formula for power sum

I simply used Newton's Interpolation method and some observation in pattern and i constructed formula for power sum.

Formula

Let's $n$ and $m$ are the integers with $n\geq 1$ and $m\geq 0$

$$\sum_{k=1}^{n} k^{m}=\sum_{b=1}^{m+1} \binom{n}b\sum_{i=0}^{b-1} (-1)^{i}(b-i)^{m}\binom{b-1}i$$

I'm not able to construct a formal proof for this formula

What is the proof?

Is this formula already exist?

Solution 1:

The Eulerian Numbers (of first kind) are explicitely defined as $$ \eqalign{ & \left\langle \matrix{ n \cr m \cr} \right\rangle = \sum\limits_{0\, \le \,k\, \le \,m} {\left( { - 1} \right)^{\,k} \left( \matrix{ n + 1 \cr k \cr} \right)\left( {m + 1 - k} \right)^{\,n} } = \cr & = \sum\limits_{0\, \le \,k\, \le \,m} {\left( \matrix{ k - n - 2 \cr k \cr} \right)\left( {m + 1 - k} \right)^{\,n} } = \cr & = \sum\limits_k {\left( \matrix{ m - k \cr m - k \cr} \right)\left( \matrix{ k - n - 2 \cr k \cr} \right)\left( {m + 1 - k} \right)^{\,n} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n - m} \right)\,} {\left( { - 1} \right)^{\,n - m + k} \left( \matrix{ n + 1 \cr m + 1 + k \cr} \right)\,k^{\,n} } = \cr & = \sum\limits_{0\, \le \,k\,\left( { \le \,n - m} \right)\,} {\left( { - 1} \right)^{\,n - m + k} \left( \matrix{ n + 1 \cr n - m - k \cr} \right)\,k^{\,n} } = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\, \le \,n - m\,} {\left( { - 1} \right)^k \left( \matrix{ n + 1 \cr k \cr} \right)\,\left( {n - m - k} \right)^{\,n} } \cr} $$

The Worpitsky's Identity then relates the monomial powers to binomials as $$ x^{\,n} = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left\langle \matrix{ n\cr j \cr} \right\rangle } \left( \matrix{ x + j \cr n \cr} \right)\quad \quad {\rm integer }n \ge 0 $$

Summing this, and using the "double convolution" identity for the binomials we get $$ \eqalign{ & \sum\limits_{0\, \le \,k\, \le \,m} k ^{\,n} = \sum\limits_{0\, \le \,k\, \le \,m} {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left\langle \matrix{ n \cr j \cr} \right\rangle } \left( \matrix{ k + j \cr n \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,m} \right)} {\sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left\langle \matrix{ n \cr j \cr} \right\rangle } \left( \matrix{ m - k \cr m - k \cr} \right)\left( \matrix{ k + j \cr k + j - n \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left\langle \matrix{ n \cr j \cr} \right\rangle } \left( \matrix{ m + j + 1 \cr m + j - n \cr} \right) = \cr & = \sum\limits_{\left( {0\, \le } \right)\,j\,\left( { \le \,n} \right)} {\left\langle \matrix{ n \cr j \cr} \right\rangle } \left( \matrix{ m + j + 1 \cr n + 1 \cr} \right) \cr} $$

Replace the Eulerian Number with its definition, change the notation to meet yours, take care of the bounds in the sums and you should confirm your formula.

Solution 2:

We try to show that

$$\sum_{k=1}^n k^m = \sum_{b=1}^{m+1} {n\choose b} \sum_{q=0}^{b-1} (-1)^q (b-q)^m {b-1\choose q}.$$

Starting from the RHS we find

$$m! [z^m] \sum_{b=1}^{m+1} {n\choose b} \sum_{q=0}^{b-1} (-1)^q {b-1\choose q} \exp((b-q)z) \\ = m! [z^m] \exp(z) \sum_{b=1}^{m+1} {n\choose b} \sum_{q=0}^{b-1} (-1)^q {b-1\choose q} \exp((b-1-q)z) \\ = m! [z^m] \exp(z) \sum_{b=1}^{m+1} {n\choose b} (\exp(z)-1)^{b-1}.$$

Now owing to the coefficient extractor and because $\exp(z)-1 = z + \cdots$ we may extend $b$ beyond $m+1$ without adding anything:

$$m! [z^m] \exp(z) \sum_{b\ge 1} {n\choose b} (\exp(z)-1)^{b-1} \\ = m! [z^m] \frac{\exp(z)}{\exp(z)-1} \sum_{b\ge 1} {n\choose b} (\exp(z)-1)^{b} \\ = - m! [z^m] \frac{\exp(z)}{\exp(z)-1} + m! [z^m] \frac{\exp(z)}{\exp(z)-1} \sum_{b\ge 0} {n\choose b} (\exp(z)-1)^{b} \\ = m! [z^m] \frac{\exp((n+1)z)-\exp(z)}{\exp(z)-1}.$$

Simplifying,

$$m! [z^m] \frac{\exp((n+1)z)-1+1-\exp(z)}{\exp(z)-1}.$$

With $m\ge 1$ we have $m! [z^m] \frac{1-\exp(z)}{\exp(z)-1} = m! [z^m] (-1) = 0,$ so we may continue with

$$m! [z^m] \frac{\exp((n+1)z)-1}{\exp(z)-1} = m! [z^m] \sum_{k=0}^n \exp(kz).$$

We get one in the sum for $k=0$ which does not contribute to $[z^m]$ and we find at last,

$$m! [z^m] \sum_{k=1}^n \exp(kz) = \sum_{k=1}^n k^m.$$

This is the claim. The sum is interesting because the RHS is an expansion of the LHS (target) into a sum of binomial coefficients in $n$ with coefficients dependend on $m.$