Expression for [tex]S_{m,n}=\sum_{k=1}^nk^m[/tex] using sum-

[shyamjayakannan]

Define [tex]S_{m,n}=\sum_{k=1}^nk^m[/tex], where [tex]m,n\in\mathbb N[/tex]. We wish to derive an expression for [tex]S_{m,n}[/tex] in terms of [tex]S_{i,n}\ \forall\ i\in\{1,\ldots,m-1\}[/tex] and will apply the sum-disturbance method on [tex]S_{m+1,n}[/tex] to do so.
So, [tex]S_{m+1,n+1}=S_{m+1,n}+(n+1)^{m+1}=1+\sum_{k=2}^{n+1}k^{m+1}=1+\sum_{k=1}^n(k+1)^{m+1}=1+\sum_{k=1}^n\sum_{r=0}^{m+1}{}^{m+1}C_rk^r=1+\sum_{r=0}^{m+1}{}^{m+1}C_r\sum_{k=1}^nk^r[/tex]
[tex]=1+\sum_{r=0}^{m+1}{}^{m+1}C_rS_{r,n}=1+\sum_{r=0}^{m-1}{}^{m+1}C_rS_{r,n}+(m+1)S_{m,n}+S_{m+1,n}[/tex]
[tex]\Rightarrow\cancel{S_{m+1,n}}+(n+1)^{m+1}=1+\sum_{r=0}^{m-1}{}^{m+1}C_rS_{r,n}+(m+1)S_{m,n}+\cancel{S_{m+1,n}}\Rightarrow S_{m,n}=\frac{1}{m+1}\left\{(n+1)^{m+1}-\sum_{r=0}^{m-1}{}^{m+1}C_rS_{r,n}-1\right\}[/tex]
So finally, we have: [tex]\boxed{\sum_{k=1}^nk^m=\frac{1}{m+1}\left\{(n+1)^{m+1}-\sum_{r=0}^{m-1}{}^{m+1}C_r\sum_{k=1}^nk^r-1\right\}}[/tex]