# Newton's Identities

This page has been identified as a candidate for refactoring.In particular: obviousUntil this has been finished, please leave
`{{Refactor}}` in the code.
Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Refactor}}` from the code. |

This article needs to be tidied.In particular: obviousPlease fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{Tidy}}` from the code. |

## Theorem

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

Define:

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

\(\ds \map {e_m} {X}\) | \(=\) | \(\ds \begin{cases} 1 & m = 0\\ \ds \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 | |||||||||||

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

Then **Newton's Identities** are:

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

\(\text {(2)}: \quad\) | \(\ds 0\) | \(=\) | \(\ds \ds \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 Viète's Formulas, Recursion Property of Elementary Symmetric Function, 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 Viète's Formulas, the calculus derivative of powers $x^n$ and logarithm $\ln \size x$, Maclaurin series expansion coefficients, mathematical induction, and Leibniz's Rule: One Variable.

### Lemma 1

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

**Proof of Lemma 1**

Begin with:

\(\text {(11)}: \quad\) | \(\ds \prod_{r \mathop = 1}^n \paren {x - x_r}\) | \(=\) | \(\ds \sum_{i \mathop = 0}^n \paren {-1}^{n - i} {\map {e_{n - i} } X} x^i\) | Viète'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:

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

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

Then:

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

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

**Proof of Lemma 2**

\(\ds \map G z\) | \(=\) | \(\ds \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:

\(\text {(14)}: \quad\) | \(\ds D^m \map F z\) | \(=\) | \(\ds \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$:

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

\(\ds \leadsto \ \ \) | \(\ds \) | \(=\) | \(\ds \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}$:

\(\ds D^{m + 1} \map F z\) | \(=\) | \(\ds \map D {\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$ | |||||||||||

\(\ds \) | \(=\) | \(\ds \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} }\) | Power Rule for Derivatives: $\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

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

**Proof of Lemma 3**

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

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

\(\ds D^{m + 1} {\map G 0}\) | \(=\) | \(\ds \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 | |||||||||||

\(\ds \paren {m + 1} {\map {e_m} X}\) | \(=\) | \(\ds \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:

\(\text {(16)}: \quad\) | \(\ds k \map {e_k} X\) | \(=\) | \(\ds \sum_{i \mathop = 1}^{k} \paren {-1}^{i - 1} {\map {e_{k - i} } X} {\map {p_i} X}\) | for $k \ge 1$, which is equation (1) |

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

Equation (16) implies:

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

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

\(\ds \leadsto \ \ \) | \(\ds 0\) | \(=\) | \(\ds \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

This page may be the result of a refactoring operation.As such, the following source works, along with any process flow, will need to be reviewed. When this has been completed, the citation of that source work (if it is appropriate that it stay on this page) is to be placed above this message, into the usual chronological ordering.In particular: Make sure that all these citations are on their appropriate proof pages. Redlinks to be resolved by implementing the appropriate material into $\mathsf{Pr} \infty \mathsf{fWiki}$.If you have access to any of these works, then you are invited to review this list, and make any necessary corrections.To discuss this page in more detail, feel free to use the talk page.When this work has been completed, you may remove this instance of `{{SourceReview}}` from the code. |

- 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*: pp. 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*: pp. 143 – 148)

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

- 1992: D.G. Mead:
*Newton's Identities*(*Amer. Math. Monthly***Vol. 99**,*no. 8*: pp. 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*: pp. 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*: pp. 1 – 5)

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