An inductive proof of Newton’s identities

by Zinovy Reichstein

Let f(x) = x^{n} + s_{1}x^{n−1} + … + s_{n−1}x + s_{n} be a monic polynomial and let x_{1}, …, x_{n} be the roots of f. Expanding the product

f(x) = (x − x_{1}) … (x − x_{n}) ,

we find that

s_{r} = (−1)^{r} ∑_{i_{1}<...<i_{i}} x_{i_{1}} … x_{i_{r}} .

The expressions s_{r} may be viewed as polynomials in x_{1}, …, x_{n}; they play an important role in algebra, combinatorics, and many other areas of mathematics. Note that each s_{r} is symmetric (i.e., it does not change if we permute x_{1}, …, x_{n}) and homogeneous of degree r. These polynomials, often called elementary symmetric polynomials^{1}, form a “basis” for all symmetric polynomials in the sense that every symmetric polynomial in x_{1}, …, x_{n} can be uniquely written as a polynomial in s_{1}, …, s_{n}.

Another important family of symmetric polynomials is given by

p_{r}(x_{1}, …, x_{n}) = x_{1}^{r} + … + x_{n}^{r} .

In fact, p_{1}, …, p_{n} also form a basis for the space of all symmetric polynomials (with rational, real or complex coefficients)^{2}.

The transition formulas between these two bases are known as “Newton’s formulas” or “Newton’s identities”; they first appeared Newton’s book Arithmetica universalis written between 1673 and 1683. If we set s_{n+1} = s_{n+2} = … = 0 then we can write them as

p_{d} + s_{1}p_{d−1} + … + s_{d−1}p_{1} + dp_{0} = 0.  (1)

Note that (1) is, in fact, a family of identities, depending on n and d, where n and d are allowed to range over the natural numbers.

1More precisely, the term “the rth elementary symmetric polynomial” usually refers to (−1)^{r}s_{r}.

2In applications of algebra to coding theory, one usually considers polynomials whose coefficients lie in a finite field. In this case s_{1}, …, s_{n} still form a basis for all symmetric polynomials but p_{1}, …, p_{n} will not do so in general. Newton’s formulas turn out to be very helpful in this setting; see, e.g., [1].

A number of proofs of Newton’s identities has appeared in the literature over the years, and new proofs continue to be published; see, e.g., [2], [3]. In this note we offer yet another proof. Denote the left hand side of (1) by F_{n}^{(d)}. Our goal is to show that F_{n}^{(d)}(x_{1}, …, x_{n}) = 0 for every n, d ∈ N. The proof proceeds by induction on m = n − d.

Since m = n − d may take on any integer value, positive or negative, the base case of our argument will cover the entire range m ≤ 0, i.e., d ≥ n. Indeed, from the definition of s_{1}, …, s_{n}, we see that

f(x_{1}) = x_{1}^{n} + s_{1}x_{1}^{n−1} + … + s_{n} = 0 ,
⋮
f(x_{n}) = x_{n}^{n} + s_{1}x_{n}^{n−1} + … + s_{n} = 0

Adding these equations together, we obtain

p_{n} + s_{1}p_{n−1} + … + +s_{n−1}p_{1} + ns_{n} = 0 .

or equivalently, F_{n}^{(n)} = 0. Similarly, expanding

x_{1}^{d−n}f(x_{1}) + … + x_{n}^{n−d}f(x_{n}) = 0 ,

we conclude that F_{n}^{(d)} = 0 for any d ≥ n.

We are now ready to perform the induction step. Choose n and d ∈ N so that m = n − d ≥ 1. Assume that F_{n′}^{(d′)} = 0 whenever n′ − d′ ≤ m − 1. We want to show that F_{n}^{(d)} = 0. First note that

F_{n}^{(d)}(x_{1}, …, x_{n−1}, 0) = F_{n−1}^{(d)}(x_{1}, …, x_{n−1}) .

(This follows from our definition of s_{r} and p_{r}; please check!) By the induction assumption F_{n−1}^{(d)}(x_{1}, …, x_{n−1}) = 0. This means that F_{n}^{(d)} is divisible by x_{n}. Since F_{n}^{(d)} is a symmetric polynomial, it is also divisible by x_{1}, …, x_{n−1}, i.e., F_{n}^{(d)} is divisible by x_{1} … x_{n}. On the other hand, note that F_{n}^{(d)} is a homogeneous polynomial of degree d < n; if it is nonzero, it cannot be divisible by x_{1} … x_{n}. Thus F_{n}^{(d)} = 0, as claimed.

References

[1] Berlekamp, E., Algebraic Coding Theory, McGraw-Hill, New York, 1968. Russian translation: Algebraicheskaya teoriya kodirovaniya, translated by I. I. Grishko, edited by S. D. Berman, Mir Publishers, Moscow, 1971.

[2] Meed, D. G., Newton’s indentities, American Math. Monthly 99, no. 8 (1992), pp. 749–751.

[3] Zeidelberg, D., A combinatorial proof of Newton’s identities, Discrete Math. 49, no. 3 (1984), p. 319.