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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: