When discussing Newton’s algorithm for polynomial interpolation in class, I was reminded of some other work that Newton had done with polynomials, known as Newton’s sums.  If a_0x^n+a_1x^{n-1}+…+a_n is a polynomial of degree n with roots r_1, r_2, … , r_n, Newton’s sums gives us an iterative method to compute r_1^k+r_2^k+…+r_n^k for k>=1 without explicitly calculating the values of the roots.  Let us denote S_k:=r_1^k+r_2^k+…+r_n^k for k>=1.  Then Newton’s sums uses the following equations to compute S_k:

a_0S_1+a_1=0

a_0S_2+a_1S_1+2a_2=0

a_0S_3+a_1S_2+a_2S_1+3a_3=0

.

.

.

a_0S_k+a_1S_1+…+ka_k=0

(where a_k is assumed to be 0 if k>n)

Since a_n, a_{n-1} are coefficients of the polynomials, we may solve for S_1 in the first equation, and then use this information to solve the second equation for S_2, and so on.  To get some kind of idea why these equations are true, we’ll consider what happens when n=k.

Suppose that we have solved S_1, S_2, …, S_{k-1}.  We have

 a_0x^n+a_1x^{n-1}+…+a_n=0,

for x=r_1, r_2, …, r_n.  Substituting x=r_1, r_2, …, r_n gives us n equations of the form a_0r_i^n+a_1r_i^{n-1}+…+a_n=0 (i=1, 2, .., n)

Summing these n equations gives us a_0S_n+a_1S_{n-1}+…+na_n=0, which is precisely what Newton’s sums tells us it should be.  Since we have the values of S_1, S_2, .., S_{n-1} by hypothesis, we can solve for S_n.  For k>n, we can use a similar trick.  Since r_i is such that

a_0r_i^n+a_1r_i^{n-1}+..+a_n=0, it is also the case that

a_0r_i^{n+1}+a_1r_i^n+…+r_ia_n=0, just by multiplying the previous equation by r_i. 

Proceeding as before, summing this previous equation over all values of i=1, 2, .., n we obtain

a_0S_{n+1}+a_1S_n+…+a_nS_1=0

which shows us how to solve for S_k for k>n. 

http://www.artofproblemsolving.com/Wiki/index.php/Newton_sums