Newton-Girard Formulas

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, b \in \Z$ be integers such that $b \ge a$.

Let $U$ be a set of $n = b - a + 1$ numbers $\set {x_a, x_{a + 1}, \ldots, x_b}$.

Let $m \in \Z_{>0}$ be a (strictly) positive integer.


Let $h_m$ be the elementary symmetric function in $U$ of degree $m$:

\(\displaystyle h_m\) \(=\) \(\displaystyle \sum_{a \mathop \le j_1 \mathop < \mathop \cdots \mathop < j_m \mathop \le b} \paren {\prod_{k \mathop = 1}^m x_{j_k} }\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{a \mathop \le j_1 \mathop < \mathop \cdots \mathop < j_m \mathop \le b} x_{j_1} \cdots x_{j_m}\)


That is, $h_m$ is the summation of the products of the elements of all distinct subsets of $U$ which have cardinality $m$.


For $r \in \Z_{> 0}$, let $S_r$ be the $r$th power sum of $U$:

$S_r = \displaystyle \sum_{k \mathop = a}^b {x_k}^r$


The Newton-Girard formula in $n$ variables of degree $m$ is:

\(\displaystyle h_m\) \(=\) \(\displaystyle \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \paren {\prod_{j \mathop = 1}^m \dfrac {\paren {\paren {-1}^{j + 1} S_j} ^{k_j} } {j^{k_j} k_j !} }\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac {\paren {-S_2}^{k_2} } {2^{k_2} k_2 !} \dfrac { {S_3}^{k_3} } {3^{k_3} k_3 !} \cdots \dfrac {\paren {\paren {-1}^{m + 1} S_m}^{k_m} } {m^{k_m} k_m !}\)


Recurrence Formula

A recurrence relation for $h_n$ can be given as:

\(\displaystyle h_n\) \(=\) \(\displaystyle \sum_{k \mathop = 1}^n \dfrac {\left({-1}\right)^{k + 1} S_k h_{n - k} } n\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac 1 n \left({S_1 h_{n - 1} - S_2 h_{n - 2} + \cdots S_n h_0}\right)\)

for $n \ge 1$.


Proof

Lemma 1

Let $G \left({z}\right)$ be the generating function for the sequence $\left\langle{h_m}\right\rangle$.

Then:

\(\displaystyle G \left({z}\right)\) \(=\) \(\displaystyle \prod_{k \mathop = a}^b \left({1 + x_k z}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({1 + x_a z}\right) \left({1 + x_{a + 1} z}\right) \cdots \left({1 + x_b z}\right)\)


Lemma 2

\(\displaystyle \ln \left({G \left({z}\right)}\right)\) \(=\) \(\displaystyle \sum_{k \mathop \ge 1} \left({-1}\right)^{k + 1} \dfrac {S_k z^k} k\)


Then:

\(\displaystyle e^{\map \ln {\map G z} }\) \(=\) \(\displaystyle \map \exp {\sum_{k \mathop \ge 1} \dfrac {\paren {-1}^{k + 1} S_k z^k} k}\) Lemma 2
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map G z\) \(=\) \(\displaystyle \prod_{k \mathop \ge 1} \map \exp {\dfrac {\paren {-1}^{k + 1} S_k z^k} k}\) Exponential of Sum
\(\displaystyle \) \(=\) \(\displaystyle \prod_{k \mathop \ge 1} \paren {\sum_{j \mathop \ge 0} \paren {\dfrac {\paren {-1}^{k + 1} S_k z^k} k}^j / j!}\) Definition of Exponential Function
\(\displaystyle \) \(=\) \(\displaystyle \prod_{k \mathop \ge 1} \paren {\sum_{j \mathop \ge 0} \paren {\dfrac {\paren {\paren {-1}^{k + 1} S_k z^k}^j} {k^j j!} } }\)
\(\displaystyle \) \(=\) \(\displaystyle \prod_{k \mathop \ge 1} \paren {1 + S_1 z + \dfrac { {S_1}^2 z^2} {2!} + \cdots} \paren {1 - \dfrac {S_2 z^2} 2 + \dfrac { {S_2}^2 z^4} {2^2 \times 2!} - \cdots} \cdots\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{m \mathop \ge 0} \paren {\sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac {\paren {-S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac {\paren {\paren {-1}^{m + 1} S_m}^{k_m} } {m^{k_m} k_m !} } z^m\)



Thus, by definition of generating function:

$h_m = \displaystyle \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac {\paren {-S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac {\paren {\paren {-1}^{m + 1} S_m}^{k_m} } {m^{k_m} k_m !}$


Examples

Order $1$

$\displaystyle \sum_{a \mathop \le i \mathop \le b} x_i = S_1$

where:

$\displaystyle S_r := \sum_{k \mathop = a}^b {x_k}^r$


Order $2$

$\displaystyle \sum_{a \mathop \le i \mathop < j \mathop \le b} x_i x_j = \dfrac 1 2 \left({\left({\sum_{i \mathop = a}^b x_i}\right)^2 - \left({\sum_{i \mathop = a}^b {x_i}^2}\right)}\right)$


Order $3$

$\displaystyle \sum_{a \mathop \le i \mathop < j \mathop < k \mathop \le b} x_i x_j x_k = \dfrac { {S_1}^3} 6 - \dfrac {S_1 S_2} 2 + \dfrac {S_3} 3$

where:

$\displaystyle S_r := \sum_{k \mathop = a}^b {x_k}^r$


Order $4$

$\displaystyle \sum_{a \mathop \le j_1 \mathop < j_2 \mathop < j_3 \mathop < j_4 \mathop \le b} x_{j_1} x_{j_2} x_{j_3} x_{j_4} = \dfrac { {S_1}^4} {24} - \dfrac { {S_1}^2 S_2} 4 + \dfrac { {S_2}^2} 8 + \dfrac {S_1 S_3} 3 - \dfrac {S_4} 4$

where:

$\displaystyle S_r := \sum_{k \mathop = a}^b {x_k}^r$.


Also known as

The Newton-Girard formulas are also known as Newton's identities.

Some sources prefer the Classical spelling formulae.


Also see


Source of Name

This entry was named for Isaac Newton and Albert Girard.


Historical Note

The Newton-Girard Formulas were discovered by Albert Girard in $1629$.

Isaac Newton rediscovered them for himself in $1666$, apparently not having known about Girard's work.

He published them in his Arithmetica Universalis of $1707$


Sources