Ha- I came here to say this - I've solved them this way for decades whenever I need one, since the derivation when I'm doodling is often quicker than finding it (or if I'm out somewhere and internet access is difficult).

Note you can use this trick for all sorts of sums, not just powers. After some experience you realize lots of sums are polynomials in the size, so just guess a polynomial without the coefficients, and plug in a few items to get the coefficients. Once you have a polynomial, you can prove the result by induction.

So, for example, summing terms of form k(k+4) from k=1 to n may be hard to look up, but you can guess the result is a polynomial of degree one more than the terms (so here, a cubic), do the generic trick, obtain the sum n(n+1)(2n+13)/6, then prove it via induction.

You can do generic items too, like sum (k+a)(k+b) to get abn + n(n+1)(3(a+b)+2n+1)/6.

It's a good technique.

Or just use Mathematica :)

The closed forms of S(n) are known and are related to Bernouilli numbers. See https://en.wikipedia.org/wiki/Faulhaber%27s_formula.

Induction is also a very good way to prove these formulas. In fact, these are just perfect textbook exercises for someone learning induction: try to find formulas for the sum of the first k-th powers (for some not so big integer k), then prove the formulas using induction. As someone else mentions, the formulas themselves are related to the Bernoulli numbers and have some surprising properties, like how formulas for odd values of k can be expressed in terms of k·(k+1)/2.

See: https://en.wikipedia.org/wiki/Lagrange_polynomial