---
tag: 459YDC1CK8
kind: proof
name: Proof of Newton's identities by a generating polynomial
msc: ["05E05"]
proves: 0WG2A3HE0S
uses: [0GYGHKX834, 0ZMY8441GW, 0AS1FZT6BM, 0CES91M79A, 0Q9EZS90GY]
sources:
  - url: https://en.wikipedia.org/wiki/Newton%27s_identities
    locator: Proofs via generating functions
---

## Proof

We compare coefficients in a polynomial identity in an extra variable $t$. This is the generating-function proof, cut off at a finite degree so that only polynomials appear.

1. Let $R$ be a [[commutative ring|0GYGHKX834]], let $n \ge 1$, and let $A = R[x_1, \dots, x_n]$ be the [[polynomial ring|0CES91M79A]]. We work in the [[polynomial ring|0Q9EZS90GY]] $A[t]$.
2. Let $e_k$ be the [[elementary symmetric polynomials|0ZMY8441GW]], with $e_0 = 1$ and $e_k = 0$ for $k > n$. Let $p_k$ be the [[power sums|0AS1FZT6BM]].
3. Let $E(t) = \prod_{i=1}^n (1 + x_i t)$. Expanding, choose $1$ or $x_i t$ from each factor. A choice is a subset $S \subseteq \set{1, \dots, n}$, and it contributes $t^{\abs{S}} \prod_{i \in S} x_i$. So $E(t) = \sum_{j \ge 0} e_j t^j$.
4. For each $i$, let $E_i(t) = \prod_{j \neq i} (1 + x_j t)$. In the same way, $E_i(t) = \sum_{j \ge 0} e^{(i)}_j t^j$. Here $e^{(i)}_j$ is the sum of the products of $j$ distinct variables other than $x_i$.
5. Fix $k \ge 1$. For each $i$, let $Q_i(t) = \sum_{m=1}^{k} (-1)^{m-1} x_i^m t^m$.
6. The product $(1 + x_i t) Q_i(t)$ telescopes: the term $(-1)^{m-1} x_i^m t^m$ of $Q_i$ cancels against $x_i t$ times the term with $m - 1$. So $(1 + x_i t) Q_i(t) = x_i t + (-1)^{k-1} x_i^{k+1} t^{k+1}$.
7. Since $E(t) = (1 + x_i t) E_i(t)$, step 6 gives $E(t) Q_i(t) = x_i t E_i(t) + (-1)^{k-1} x_i^{k+1} t^{k+1} E_i(t)$.
8. Summing over $i$, and using $\sum_i Q_i(t) = \sum_{m=1}^{k} (-1)^{m-1} p_m t^m$, we get
$$E(t) \sum_{m=1}^{k} (-1)^{m-1} p_m t^m = \sum_{i=1}^n x_i t E_i(t) + t^{k+1} H(t)$$
for some $H(t) \in A[t]$.
9. The coefficient of $t^k$ on the left is $\sum_{m=1}^{k} (-1)^{m-1} e_{k-m} p_m$, by step 3. The term $t^{k+1} H(t)$ has no $t^k$ term.
10. By step 4, the coefficient of $t^k$ in $\sum_i x_i t E_i(t)$ is $\sum_{i=1}^n x_i e^{(i)}_{k-1}$.
11. Each term of $x_i e^{(i)}_{k-1}$ is $\prod_{j \in S} x_j$ for a $k$-element set $S$ with $i \in S$. So each $k$-element set $S$ appears once for each $i \in S$, that is, $k$ times. Hence $\sum_i x_i e^{(i)}_{k-1} = k \, e_k$.
12. This also holds for $k > n$, where both sides are $0$, since there are no $k$-element subsets.
13. Comparing the coefficients of $t^k$ in step 8 gives $k \, e_k = \sum_{i=1}^{k} (-1)^{i-1} e_{k-i} \, p_i$ for every $k \ge 1$.

## Idea

The polynomial $E(t) = \prod (1 + x_i t)$ has the $e_k$ as coefficients. Multiplying it by an alternating sum of power sums gives $t$ times the derivative of $E(t)$, up to terms of high degree. The coefficient of $t^k$ in $t E'(t)$ is $k e_k$, which gives the identity.