sum-guest

The sum of S(n) = 1^k + 2^k + ... + n^k is a polynomial of degree k + 1 over n. To find a closed form for S(n) you only need to compute k + 2 points, e.g. S(0), S(1), ..., S(k + 1) and fit a polynomial.

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 :)