The identity of a polynomial sum

Question

I am wondering if there is a recursive formula to calculate $$S=1^{k}+2^{k}+3^{k}+\dots+n^{k}$$ Where $k$ and $n$ are natural numbers.

Answer 1

I believe this should do,

$$f[k][n]=f[k][n-1]+(f[k-1][n]-f[k-1][n-1])\cdot n$$

where $f[k][n] = 1^k+2^k+\dots+n^k$. so we get $n^{k-1} = (f[k-1][n]-f[k-1][n-1])$ and multiplying both side with $n$ we get $n^k=(f[k-1][n]-f[k-1][n-1])\cdot n$.

And $f[k][n-1]+n^k = f[k][n]$