Formula for $1^k+2^k+3^k...n^k$ for $n,k \in \mathbb{N}$ So I've been looking for a formula where I can input the parameter $k$ and it will give me a formula for $1^k+2^k+3^k...+ n^k$ with $n,k \in \mathbb{N}$. The result is always a polynomial with $k+1$ as highest power. I've taken the time to calculate the polynomes for $k=1$ to $k=10$ by hand and using the interpolation feature of Wolfram Alpha. Here are the results (I'll only show the coefficients for the sake of clarity. the coefficients are always from $n^{k+1}$ to $n^1$. the constant is always $0$. So $\frac{1}{2},-\frac{1}{2}$ becomes $\frac{1}{2}n^2-\frac{1}{2}n$):


*

*$k=1$ : $\frac{1}{2},-\frac{1}{2}$

*$k=2$ : $\frac{1}{3},\frac{1}{2},\frac{1}{6}$

*$k=3$ : $\frac{1}{4},\frac{1}{2},\frac{1}{4},0$

*$k=4$ : $\frac{1}{5},\frac{1}{2},\frac{1}{3},0,-\frac{1}{30}$

*$k=5$ : $\frac{1}{6},\frac{1}{2},\frac{5}{12},0,-\frac{1}{12},0$

*$k=6$ : $\frac{1}{7},\frac{1}{2},\frac{1}{2},0,-\frac{1}{6},0,\frac{1}{42}$

*$k=7$ : $\frac{1}{8},\frac{1}{2},\frac{7}{12},0,-\frac{7}{24},0,\frac{1}{12},0$

*$k=8$ : $\frac{1}{9},\frac{1}{2},\frac{2}{3},0,-\frac{7}{15},0,\frac{2}{9},0,-\frac{1}{30}$

*$k=9$ : $\frac{1}{10},\frac{1}{2},\frac{3}{4},0,-\frac{7}{10},0,\frac{1}{2},0,-\frac{3}{20},0$

*$k=10$ : $\frac{1}{11},\frac{1}{2},\frac{5}{9},0,1,0,1,0,-\frac{1}{2},0,\frac{5}{66}$


There are a few things i notice: Firstly, the coefficient of the highest power seems to be $\frac{1}{k+1}$. Secondly, the coefficient of the second highest power seems to be $\frac{1}{2}$ with the exception of $k=1$. Thirdly, all coefficients of the fourth, sixth, eight highest power and so on seem to be $0$. 
What is the formula that will output the coefficients for any value of $k$?

Another way to derive a formula for $$S(k,n)=\sum_{s=1}^{n}{s^k}$$ is to use the binomial expansion. To do this, you can start by changing the summation index $s$ to $t+1$. That is:$$S(k,n)=\sum_{t=0}^{n-1}{(t+1)^k}=1+\sum_{t=1}^{n-1}{(t+1)^k}$$Using binomial expansion we have:$$S(k,n)=1+\sum_{t=1}^{n-1}{\sum_{j=0}^{k}{\binom{k}{j}t^j}}$$Changing the order of summation (notice the independence) gets:$$S(k,n)=1+\sum_{j=0}^{k}{\sum_{t=1}^{n-1}{\binom{k}{j}t^j}}=1+\sum_{j=0}^{k}{\left(\binom{k}{j}\sum_{t=1}^{n-1}{t^j}\right)}$$The inner sum equals $S(j,n-1)$, so: $$S(k,n)=1+\sum_{j=0}^{k}{\binom{k}{j}S(j,n-1)}$$Now, by excluding the last two terms of the summation (the terms obtained by $j=k-1$ and $j=k$) we finally get: $$S(k,n)=1+S(k,n-1)+kS(k-1,n-1)+\sum_{j=0}^{k-2}{\binom{k}{j}S(j,n-1)}$$ Since $S(k,n)-S(k,n-1)=n^k$: $$S(k-1,n-1)=\frac{1}{k}\left(n^k-1-\sum_{j=0}^{k-2}{\binom{k}{j}S(j,n-1)}\right)$$ The formula shows a recursive relation between $S(k-1,n-1)$ and lower sums, i.e., $S(0,n-1),S(1,n-1),\dots,S(k-2,n-1)$. By changing $k$ to $k+1$ and $n$ to $n+1$ the original format emerges: $$S(k,n)=\frac{1}{k+1}\left((n+1)^{k+1}-1-\sum_{j=0}^{k-1}{\binom{k+1}{j}S(j,n)}\right)$$ You can now start from $S(0,n)=n$ and derive $S(k,n)$ for $k=1,2,\dots$. For example: $$S(1,n)=\frac{1}{2}\left( (n+1)^2-1-\binom{2}{0}S(0,n)\right)=\frac{1}{2}\left( n^2+2n+1-1-n \right)=\frac{1}{2}n(n+1)$$
