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?
 A: 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.
A: 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.$
A: 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$
