Newton's Identities

From ProofWiki
(Redirected from Newton-Girard Formulas)
Jump to navigation Jump to search


This page has been identified as a candidate for refactoring of basic complexity.
In particular: historical note
Until this has been finished, please leave {{Refactor}} in the code.

New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only.

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: obvious
Please 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 < \cdots < 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 \le m \le n \\ 0 & : m > n \\ \end {cases}\) Definition of 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}\) Definition of Power Sum

Then Newton's identities are:

\(\text {(1)}: \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 $1 \le k \le n$
\(\text {(2)}: \quad\) \(\ds 0\) \(=\) \(\ds \sum_{i \mathop = k - n}^k \paren {-1}^{i - 1} \map {e_{k - i} } X \map {p_i} X\) for $1 \le n < k$



This article is complete as far as it goes, but it could do with expansion.
In particular: Implement a simplified version
You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding this information.
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 {{Expand}} from the code.
If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.


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 in 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 in 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$


Also known as

Newton's identities are also known as:

the Newton-Girard identities
the Newton-Girard formulas

for Albert Girard.


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.


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.
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.


Retrieved from "https://proofwiki.org/w/index.php?title=Newton%27s_Identities&oldid=657724"