# 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?

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.

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

• Thank you so much.... – Pruthviraj Feb 13 at 18:35

You can try from telescopic series:

$$\displaystyle\sum_{k=1}^n t_{k+1}-t_k=t_{n+1}-t_1$$

and apply to :

$$\displaystyle\sum_{k=1}^n (k+1)^{m}-k^m = (n+1)^m-1^m$$

The idea is the same as follows:

for $$m=3$$:

$$(n+1)^3-1 = \displaystyle\sum_{k=1}^n (k+1)^{ 3}-k^3 = \displaystyle\sum_{k=1}^n k^3+3k^2+3k+1-k^3=3\sum k^2+3\sum k$$

and you have to know the sum of $$k$$'s and $$k^2$$'s with the same method:

for $$m=2$$:

$$(n+1)^2-1 = \displaystyle\sum_{k=1}^n (k+1)^{ 2}-k^2 = \displaystyle\sum_{k=1}^n k^2+2k+1-k^2=2\sum k+\sum 1$$

as you see, if you want $$S_k=\sum_{k=1}^n k^m$$, you will need $$S_{k-1}, S_{k-2}, \cdots , S_1,S_0$$

• But then result also need prove $$(n+t)^{m}=\sum_{b=0}^{m+1} \binom{n}b\sum_{i=0}^{b} (-1)^{i}(b-i+t)^{m}\binom{b}i$$ such that $n$ and $m$ belongs to natural number and $t$ belongs to real number – Pruthviraj Jun 17 '19 at 21:04