The claim that 1 + 2 + ... + n = n (n + 1) / 2 only requires you to verify it for n = 0, n = 1, and n = 2, e.g. that 0 = 0 * 1 /2, 1 = 1 * 2 / 2, and 1 + 2 = 2 * 3 / 2. I found this really surprising when I first heard it and thought I'd share :)
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 :)