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.

Very elementary method: knowing that $S(n) = \sum_{k=1}^n k^p = a_{p+1}n^{p+1}  + \cdots + a_1 n + a_0$, you can calculate the coefficients using limits:
$$a_{p+1} = \lim_{n\to\infty}\frac{S(n)}{n^{p+1}} =
\lim_{n\to\infty}\frac{1^p+\cdots+n^p}{n^{p+1}} =
\lim_{n\to\infty}\frac{(n+1)^p}{(n+1)^{p+1}-n^{p+1}} = \cdots =
\frac1{p+1}.$$
(Cesàro-Stolz used in the third =)
You can continue with
$$a_p = \lim_{n\to\infty}\frac{S(n)-a_{p+1}n^{p+1}}{n^p} = \cdots$$
$$\cdots$$
