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

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 $n$th 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.