Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula As far as every question I've seen concerning "what is $\sum_{k=1}^nk^p$" is always answered with "Faulhaber's formula" and that is just about the only answer.  In an attempt to make more interesting answers, I ask that this question concern the problem of "Methods to compute $\sum_{k=1}^nk^p$ without Faulhaber's formula for fixed $p\in\mathbb N$".  I've even checked this post of common questions without finding what I want.
Rule #1:
Any method to compute the sum in question for arbitrary $p$ is good, either recursively or in some manner that is not in itself a closed form solution.  Even algorithms will suffice.
Rule #2:
I don't want answers confined to "only some values of $p$".  (A good challenge I have on the side is a generalized geometric proof, as that I have not yet seen)
Exception: If your answer does not generalize to arbitrary $p$, but it still generalizes to an infinite amount of special $p$'s, that is acceptable.
Preferably, the method is to be easily applied, unique, and interesting.
To start us off, I have given my answer below and I hope you all enjoy.

By the binomial theorem, $$(x+1)^{n+1}=\sum_{h=0}^{n+1} {n+1 \choose h}x^h$$
$$(x+1)^{n+1}-x^{n+1}=\sum_{h=0}^n {n+1 \choose h}x^h$$
Sum this equality for $x=0,1\dotsb k$
$$\sum_{x=1}^k((x+1)^{n+1}-x^{n+1})=(k+1)^{n+1}-1=\sum_{x=1}^k\sum_{h=0}^n {n+1 \choose h}x^h=\sum_{h=0}^n{n+1 \choose h}\sum_{x=1}^kx^h=(n+1)\sum_{x=1}^kx^h+\sum_{h=0}^{n-1}{n+1 \choose h}\sum_{x=1}^kx^h$$
Which means $$(n+1)\sum_{x=1}^kx^n=(k+1)^{n+1}-1-\sum_{h=0}^{n-1}{n+1 \choose h}\sum_{x=1}^kx^h$$
So you can find the sum of the $n$th powers if you have all the previous ones. The base case is
$$\sum_{x=1}^kx^0=k$$
Then
$$\sum_{x=1}^kx^1=\frac{1}{2}\left((k+1)^2-1-{2 \choose 0}k\right)=\frac{k^2+k}{2}$$
$$\sum_{x=1}^kx^2=\frac{1}{3}\left((k+1)^3-1-{3 \choose 0} k - {3 \choose 1} \frac{k^2+k}{2}\right)=\frac{k^3}{3}+\frac{k^2}{2}+\frac{k}{6}$$
Etcetera.
