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

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 at 21:04