# Newton's Identities

## Contents

## Theorem

Let $X$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.

Define:

\(\displaystyle {\mathbf S}_m\) | \(=\) | \(\displaystyle \set { \paren {j_1,\ldots,j_m} : 1 \le j_1 \lt \cdots \lt j_m \le n}\) | $1 \le m \le n$ | ||||||||||

\(\displaystyle \map {e_m} {X}\) | \(=\) | \(\displaystyle \begin{cases} 1 & m = 0\\ \displaystyle \sum_{ {\mathbf S}_m } x_{j_1} \cdots x_{j_m} & 1 \leq m \leq n \\ 0 & m \gt n \\ \end{cases}\) | elementary symmetric function | ||||||||||

\(\displaystyle \map {p_k} X\) | \(=\) | \(\displaystyle \begin{cases} \displaystyle n & k = 0 \\ \displaystyle \sum_{i \mathop = 1}^n x_i^k & k \ge 1 \\ \end{cases}\) | power sums |

Then **Newton's Identities** are:

\((1):\quad\) | \(\displaystyle k \, \map {e_k} X\) | \(=\) | \(\displaystyle \displaystyle \sum_{i \mathop = 1}^k \paren {-1}^{i-1} \map {e_{k-i} } X \map {p_i} X\) | for $1 \leq k \leq n$ | |||||||||

\((2):\quad\) | \(\displaystyle 0\) | \(=\) | \(\displaystyle \displaystyle \sum_{i \mathop = k-n}^k \paren {-1}^{i-1} \map {e_{k-i} } X \map {p_i} X\) | for $1 \leq n \lt k$ |

## Proof 1

### Outline

The proof is divided into three cases: $k < n$, $k=n$ and $k>n$.

The tools are Viete's Formulas, symmetric function recursion, telescoping sums and homogeneous functions of degree $k$.

## Proof 2

### Outline

Calculus is used to prove identities (1) and (2) in a single effort.

The tools are Viete's Formulas, the calculus derivative of powers $x^n$ and logarithm $\ln \vert x \vert$, Maclaurin series expansion coefficients, mathematical induction, and Leibniz's Rule: One Variable.

### Lemma 1

\(\displaystyle \prod_{r \mathop = 1}^n \paren { 1 + x_r z }\) | \(=\) | \(\displaystyle \sum_{m \mathop = 0}^n {\map {e_m} X} z^m\) |

**Proof of Lemma 1**

Begin with:

\((11):\quad\) | \(\displaystyle \displaystyle \prod_{r \mathop = 1}^n \paren { x - x_r }\) | \(=\) | \(\displaystyle \sum_{i \mathop = 0}^n \paren {-1}^{n-i} {\map {e_{n-i} } X} x^i\) | Viete's Formulas |

Change variables in (11): $x = -1/z$.

Details: Generating Function for Elementary Symmetric Function.

$\Box$

### Lemma 2

Denote by $D^k \map f z$ the $k$th calculus derivative of $\map f z$.

Let:

\(\displaystyle \map G z\) | \(=\) | \(\displaystyle \displaystyle \prod_{k \mathop = 1}^n \paren {1 + x_k z}\) | as in Lemma 1 | ||||||||||

\(\displaystyle \map F z\) | \(=\) | \(\displaystyle \dfrac { \map {DQ} z }{\map Q z}\) | the calculus derivative of $\ln \vert { \map Q z } \vert$ |

Then:

\((12):\quad\) | \(\displaystyle \dfrac { D^m \map G {0} } { m! }\) | \(=\) | \(\displaystyle \map { e_m } X\) | ||||||||||

\((13):\quad\) | \(\displaystyle \dfrac { D^m \map F {0} } { m! }\) | \(=\) | \(\displaystyle \paren {-1}^m \map {p_{m+1} } X\) |

**Proof of Lemma 2**

\(\displaystyle \map G z\) | \(=\) | \(\displaystyle \sum_{m \mathop = 0}^n {\map {e_m} X} z^m\) | by Lemma 1 |

Then identity (12) holds by Maclaurin series expansion applied to polynomial $G$.

Identity (13) will be proved after mathematical induction establishes (14) *infra*.

Let $\map {\mathbf P} m$ be the statement:

\((14):\quad\) | \(\displaystyle D^m \map F z\) | \(=\) | \(\displaystyle \sum_{i \mathop = 1}^n \dfrac{ m!\paren {-1}^m x_i^{m+1} }{ \paren { 1 + x_i z }^{m+1} }\) | for $m \ge 0$ |

Basis for the induction: $m=0$

By calculus and the definition of $G$:

\(\displaystyle \map F z\) | \(=\) | \(\displaystyle \dfrac { D \map Q z}{\map Q z}\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \displaystyle \sum_{i \mathop = 1}^n \dfrac { x_i }{ 1 + x_i z }\) |

Then $\map {\mathbf P} 0$ is true.

Induction step $\map {\mathbf P} m$ implies $\map {\mathbf P} {m+1}$:

\(\displaystyle D^{m+1} \map F z\) | \(=\) | \(\displaystyle D \paren {\sum_{i \mathop = 1}^n \dfrac{ m!\paren {-1}^m x_i^{m+1} }{ \paren { 1 + x_i z }^{m+1} } }\) | by induction hypothesis $\map {\mathbf P} m$ | ||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \sum_{i \mathop = 1}^n \dfrac{ m! \paren {-1}^m x_i^{m+1} \, \paren {-1} \paren {m+1} \, x_i}{ \paren { 1 + x_i z }^{m+2} }\) | by calculus power rule $\dfrac { \d u^{-n} }{ \d z } = \paren { -n } u^{-n-1} \dfrac { \d u }{ \d z }$ |

Simplify to prove $\map {\mathbf P} {m+1}$ is true.

The induction is complete.

To prove equation (13), first let $z=0$ in equation (14).

Divide by $m!$ to isolate $\map {p_{m+1} } X$, which proves (13).

$\Box$

### Lemma 3

\((15):\quad\) | \(\displaystyle \paren {m+1} \map {e_{m+1} } X\) | \(=\) | \(\displaystyle \displaystyle \sum_{r \mathop = 0}^m \paren {-1}^r { \map {e_{m-r} } X } { \map {p_{r+1} } X }\) | for $m \geq 0$ |

**Proof of Lemma 3**

Begin with $D \map G z = {\map F z} {\map G z}$ and differentiate $m$ times on variable $z$:

\(\displaystyle D^{m+1} \map G z\) | \(=\) | \(\displaystyle \displaystyle \sum_{r \mathop = 0}^m {\dbinom {m} {r} } D^r {\map F z} \, D^{m-r} {\map G z}\) | Leibniz's Rule/One Variable | ||||||||||

\(\displaystyle D^{m+1} {\map G 0}\) | \(=\) | \(\displaystyle \displaystyle \sum_{r \mathop = 0}^m \dbinom {m} {r} r! \, \paren {-1}^r {\map { p_{r+1} } X} \, \paren {m-r}! \, {\map {e_{m-r} } X}\) | Evaluate at $ z = 0$ and use equations (12) and (13) in Lemma 2. | ||||||||||

\(\displaystyle \paren {m+1} {\map {e_m} X}\) | \(=\) | \(\displaystyle \displaystyle \sum_{r \mathop = 0}^m \paren {-1}^r {\map {e_{m-r} } X} \, {\map {p_{r+1} } X}\) | Use (12), then collect factorials and simplify. |

$\Box$

**Proof of the Theorem**

To prove (1), start with equation (15) in Lemma 3.

Change indices via equations $m+1=k$, $r+1=i$.

The summation is from $i=0+1$ to $i=m+1$, which gives range $i=1$ to $k$.

Subscript $m-r$ equals $k-1-i+1$, which simplifies to $k-i$.

Then:

\((16):\quad\) | \(\displaystyle k \, { \map {e_{k} } X }\) | \(=\) | \(\displaystyle \displaystyle \sum_{i \mathop = 1}^{k} \paren {-1}^{i-1} { \map {e_{k-i} } X } { \map {p_{i} } X }\) | for $k \geq 1$, which is equation (1) |

To prove (2), assume $k > n \ge 1$ and $X = \set {x_1,\ldots,x_n}$.

Equation (16) implies:

\((117):\quad\) | \(\displaystyle 0\) | \(=\) | \(\displaystyle k \, { \map {e_{k} } X }\) | because $ \map {e_{j} } X = 0$ for $j=n+1,\ldots,k$. | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 0\) | \(=\) | \(\displaystyle \sum_{i \mathop = 1}^{k} \paren {-1}^{i-1} { \map {e_{k-i} } X } { \map {p_{i} } X }\) | by (16) for $k \geq 1$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle 0\) | \(=\) | \(\displaystyle \sum_{i \mathop = k-n}^{k} \paren {-1}^{i-1} { \map {e_{k-i} } X } { \map {p_{i} } X }\) | because $ \map {e_{k-i} } X = 0$ when $n+1 \le k-i \le k$ |

Then (2) holds.

$\blacksquare$

## Source of Name

This entry was named for Isaac Newton.

## Historical Note

Isaac Newton published in *Arithmetica universalis* (1707) a generalization of the $ n \le 4$ formulas of A. Girard (1629), without proof. Formulas (1)-(2) make it possible to recursively solve for the symmetric functions $\set {e_k} $ in terms of power sums $\set {p_k}$ (Knuth 1997, p 94) and conversely. A history of Girard's work is in Funkhouser (1930). Various proofs of (1)-(2) exist: Baker (1959), Eidswick (1968), Mead (1992), Kalman (2000), Tignol (2001). Boklan (2018) reported calculus differentiation recursions to directly generate Girard's identities.

## Also named as

Newton-Girard Identities, Newton-Girard Formulas.

## Sources

- 1720: Isaac Newton and Edm. Halley:
*Universal Arithmetick, Or, A Treatise of Arithmetical Composition and Resolution*

- 1930: H. Gray Funkhouser:
*A Short Account of the History of Symmetric Functions of Roots of Equations*(*Amer. Math. Monthly***Vol. 37**,*no. 7*: 357 – 365) www.jstor.org/stable/2299273

- 1959: George Baker:
*A New Derivation of Newton’s Identities and Their Application to the Calculation of the Eigenvalues of a Matrix*(*Journal of the SIAM***Vol. 7**,*no. 2*: 143 – 148)

- 1968: J.A. Eidswick:
*A Proof of Newton’s Power Sum Formulas*(*Amer. Math. Monthly***Vol. 75**,*no. 4*: 396 – 397) www.jstor.org/stable/2313436

- 1992: D.G. Mead:
*Newton's Identities*(*Amer. Math. Monthly***Vol. 99**,*no. 8*: 749 – 751) www.jstor.org/stable/2324242

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.): $\S 1.2.9$: Generating Functions: Exercise $10$

- 2000: Dan Kalman:
*A Matrix Proof of Newton's Identities*(*Math. Mag.***Vol. 73**,*no. 4*: 313 – 315) www.jstor.org/stable/2690982

- 2004: Jean-Pierre Tignol:
*Galois' theory of algebraic equations*(Reprinted ed.): Newton's Identities**(please cite chapter and section in the standard format)**

- 2018: Kent D. Boklan:
*A note on identities for elementary symmetric and power sum polynomials*(*Discrete Math, Algorithm, Appl.***Vol. 10**,*no. 1*: 1 – 5)

- Weisstein, Eric W. "Newton-Girard Formulas." From
*MathWorld*--A Wolfram Web Resource. http://mathworld.wolfram.com/Newton-GirardFormulas.html.html