A blog for enthusiastic math-lovers!

Archive for July, 2012

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


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


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


(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}).


Tag Cloud