Posted by: holdenlee | November 22, 2010

Newton Sums


Let x_1,x_2,\ldots be variables. In this post we develop the Newton formulas relating the symmetric polynomials in the x_i

\displaystyle s_n=\sum_{1\leq i_1<\cdots <i_n}x_{i_1}x_{i_2}\cdots x_{i_n}

and the power sums

\displaystyle p_n=\sum_{i\geq 1} x_i^n.

(For example, when we have 3 variables, s_2=x_1x_2+x_1x_3+x_2x_3 and p_2=x_1^2+x_2^2+x_3^2. For convenience of notation we don’t restrict the number of variables; if we are working with k variables we could just set 0=x_{k+1}=x_{k+2}=\cdots . By convention s_0=1.)

We note that the s_i and p_i are the coefficients of powers of t of the following generating functions.

\displaystyle S(t)=\prod_{i\geq 1} (1+x_it)=1+s_1t+s_2t^2+\cdots

\displaystyle P(t)=\sum_{i\geq 1}\frac{x_i}{1-x_it}=\sum_{i\geq 1} (x_i+x_i^2t+\cdots)=p_1+p_2t+\cdots

Why do these expansions hold? Each term in the expansion of S(t) is a term of the form x_{i_1}\cdots x_{i_n}t^n where the x_{i_j} are distinct, since we can only get a factor of x_{i_j} from the factor (1+x_{i_j}t). Since each x_i always comes with a factor of t, t acts as a “counter” giving the total number of variables. Grouping the terms with t^n we get all combinations of products of n of the x_i.

For P(t) the argument is simpler: expand in geometric series as shown above to get that the coefficients of t^{n-1} are the nth powers of the x_i.

We want an identity involving s_i and p_i so we look for an identity involving S(t) and P(t). First we turn the 1+xt_i into 1-x_it: define

\displaystyle \Psi(t)=S(-t)=\prod_{i\geq 1} (1-x_it)=1-s_1t+s_2t^2-s_3t^3+\cdots.

Now take the logs of both sides (thinking of the above as a formal series in t):

\displaystyle \ln(\Psi(t))=\sum_{i\geq 1} \ln(1-x_it).

Now differentiate both sides.

\displaystyle \frac{\Psi'(t)}{\Psi(t)}=-\sum_{i\geq 1} \frac{x_i}{1-x_it}.

The right-hand side is just -P(t) (TA-DA!). Thus we get

\displaystyle -\Psi'(t)=\Psi(t)P(t).

Now we match coefficients of t^{n-1} on both sides. Note

\displaystyle -\Psi'(t)=s_1-2s_2t+3s_3t^2-\cdots

so the coefficient of t^{n-1} is (-1)^{n+1}n s_n. To get the coefficients of the right-hand side, note that a term containing t^{n-1} on the RHS comes from multiplying (-1)^is_it^i in \Psi(t) and a term p_{n-i}t^{n-i-1} in P(t). Thus the coefficients of t^{n-1} are

\displaystyle (-1)^{n+1}ns_n=\sum_{i=0}^{n-1}(-1)^is_ip_{n-i}=s_0p_n-s_1p_{n-1}+\cdots +(-1)^{n-1}s_{n-1}p_1

which is the Newton sum formula.

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

Categories

%d bloggers like this: