(12C Platinum) Sums of Powers of N numbers

[Albert Chan]

From another thread about forward difference table, we can treat sum of powers on N numbers as polynomial interpolation.

For sum of kth powers, we expect a polynomial with degree k+1

Example, for sum of cubes, just use forward differences of cubes of 4 numbers

1 8 27 64
7 19 37
12 18
6

Thus sum of cubes formula = \(1\binom{n}{1}+7\binom{n}{2}+12\binom{n}{3}+6\binom{n}{4} = [n(n+1)/2]^2
\)

We can also do interpolation with 5 points. (5 points "fixed" a quartic polynomial)
Example, for sum of cubes of 10 numbers, interpolate for N=10:

Code:

N Sum Intepolation for N=10
4 100
3 36  484
2 9   373  1261
1 1   298  1135  2269
0 0   250  1030  2185  3025

All the intepolations above are simple linear interpolation.
Example, 1030 is from interpolation of 2 points (3, 484), (0, 250), for N=10