## A blog for enthusiastic math-lovers!

### Newton sums!

Newton sums is a very useful concept to understand for much of contest math because it pops up in many different ways. It is a tool that allows you to take a polynomial P(x) and evaluate the sum of the roots, the sum of the squares of the roots, the sum of the cubes of the roots, etc. in terms of coefficients and other sums.

Consider a polynomial P(x) of degree n,
$P(x) = a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$

Let P(x)=0 have roots $x_1,x_2,\ldots,x_n.$ Define the following sums:

$S_1 = x_1 + x_2 + \cdots + x_n$

$S_2 = x_1^2 + x_2^2 + \cdots + x_n^2$

$\vdots$

$S_k = x_1^k + x_2^k + \cdots + x_n^k$

$\vdots$

Newton sums tell us that,

$a_nS_1 + a_{n-1} = 0$

$a_nS_2 + a_{n-1}S_1 + 2a_{n-2}=0$

$a_nS_3 + a_{n-1}S_2 + a_{n-2}S_1 + 3a_{n-3}=0$

$\vdots$

(Define $a_j = 0$ for $j<0$.)

(The above definition was taken from AoPS http://www.artofproblemsolving.com/Wiki/index.php/Newton%27s_Sums)

We can apply these Newton’s sums to a variety of problems. One such problem is from AIME 2003. It states:

Consider the polynomials $P(x) = x^{6} - x^{5} - x^{3} - x^{2} - x$ and $Q(x) = x^{4} - x^{3} - x^{2} - 1$. Given that $z_{1},z_{2},z_{3},$ and $z_{4}$ are the roots of $Q(x) = 0$, find $P(z_{1}) + P(z_{2}) + P(z_{3}) + P(z_{4})$.