Closed form for $1^k + ... + n^k$ (generalized Harmonic number) This question must have been asked, it's just very hard to search for such questions.
I'm looking for the cleanest method I can find for getting a closed form formula for $\sum_{i=1}^n i^k$
Wikipedia provides https://en.wikipedia.org/wiki/Faulhaber%27s_formula which has a tantalising "There is also a similar (but somehow simpler) expression:..." paragraph but fails to follow up.
http://www.maa.org/press/periodicals/convergence/sums-of-powers-of-positive-integers-conclusion contains a thorough "through the ages" expose, the last two entries being Pascal and Bernoulli.
However, https://www.youtube.com/watch?v=8nUZaVCLgqA seems to contain a fresh approach that I can't find documented anywhere else. However, I find the video hard to follow.
And maybe there is some technique that is cleaner still...
I understand that "cleanest" is maybe subjective and hence it is an imperfect question, but it would be interesting to see the various alternatives (and surely there cannot be many) battle it out.
 A: Put
$$
S_\ell(n):=\sum_{i=1}^{n}i^{\ell}
$$
and consider the identity
$$
(n+1)^{k+1}-1=\sum_{i=1}^{n}[(i+1)^{k+1}-i^{k+1}]=(k+1)S_k(n)+\binom{k+1}{2}S_{k-1}(n)+\ldots+\\+\binom{k+1}{k}S_1(n)+n.
$$
Then, if you know the sums 
for $\ell=1,\ldots,k-1$, you can calculate $S_k(n)$  with the above recursive relation.
For example,
$$
(n+1)^2-1=2S_1(n)+n\Rightarrow S_1(n)=\frac12[(n+1)^2-1-n]=\frac12n(n+1),\\
(n+1)^3-1=3 S_2(n)+3S_1(n)+n\Rightarrow S_2(n)=\frac13[n^3+3n^2+3n-n-3S_1(n)]\Rightarrow\\
\Rightarrow S_2(n)=\frac{n^3}{3}+\frac{n^2}{2}+\frac{n}{6}
$$
A: Having posted a much similar question recently, I'm inclined to provide you with my somewhat unique answer.

$$a_p=1-p\int_0^1f(t,p-1)dt,\quad f(x,0)=x$$
$$f(x,p)=a_px+p\int_0^xf(t,p-1)dt$$
$$f(x,p)=\sum_{k=1}^xk^p$$
Easy enough to see that
$$x=\sum_{k=1}^xk^0$$
Also relatively easy to find that
$$a_1=1-\int_0^1t\ dt=\frac12\implies f(x,1)=\frac12x+\int_0^xt\ dt=\frac12x+\frac12x^2=\sum_{k=1}^xk^1$$
And you can keep going with this.  Requires very little calculus skill to do.
