Newton's Identities/Proof 1

From ProofWiki
Jump to navigation Jump to search

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\\ \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
\(\ds \map {p_k} X\) \(=\) \(\ds \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:

\(\text {(1)}: \quad\) \(\ds k \, \map {e_k} X\) \(=\) \(\ds \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$
\(\text {(2)}: \quad\) \(\ds 0\) \(=\) \(\ds \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

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


Details


Discovery of formulas (1)-(2) has humble beginnings:

\(\text {(3)}: \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

Create $n$ equations all with left hand side zero by substitution $x = x_j$ in (3), $1 \le j \le n$.

Then multiply the $j$th equation by $x_j^r$ and add the $n$ equations, for $1 \le j \le n$:

\(\text {(4)}: \quad\) \(\ds 0\) \(=\) \(\ds \sum_{j \mathop = 1}^n \sum_{i \mathop = 0}^n \paren {-1}^{n - i} \map {e_{n - i} } X x_j^{i + r}\)
\(\ds \) \(=\) \(\ds \sum_{i \mathop = 0}^n \paren {-1}^{n - i} \map {e_{n - i} } X \map {p_{i + r} } X\) Term $\map {e_m} X$ is zero for $m \gt n$, affecting case $r \gt 0$.

Case $r = 0$ in (4) gives (1) for $k = n$, by isolating term $n \map {e_n} X$.

Case $r > 0$ in (4) gives (2) by re-indexing: $m = k - n + i$ with $m = k - n$ to $k$.


Case $k < n$ in (1), not yet discussed, does not use multiply and add as in (4).

The key ingredient:

\(\text {(5)}: \quad\) \(\ds \map {e_m} {z_1, \ldots, z_p, z_{p + 1} }\) \(=\) \(\ds z_{p + 1} \map {e_{m - 1} } {z_1, \ldots, z_p} + \map {e_m} {z_1, \ldots, z_p}\) Recursion Property of Elementary Symmetric Function, valid for $1 \le m \le p$.

The right hand side of (1) is:

\(\text {(6)}: \quad\) \(\ds \) \(\) \(\ds \sum_{i \mathop = 1}^k \paren {-1}^{i - 1} \sum_{j \mathop = 1}^n \map {e_{k - i} } X x_j^i\) Replace in (1) each power sum $p_i$ by its summation.
\(\ds \leadsto \ \ \) \(\ds \) \(\) \(\ds \paren {-1}^{k - 1} \sum_{m \mathop = 0}^{k - 1} \paren {-1}^m \sum_{j \mathop = 1}^n \map {e_m} X x_j^{k - m}\) Re-index with $m = k - i$ and adjust powers of $-1$.
\(\ds \leadsto \ \ \) \(\ds \) \(\) \(\ds \paren {-1}^{k - 1} \sum_{j \mathop = 1}^n \paren {\map {e_0} X x_j^k + \sum_{m \mathop = 1}^{k - 1} \paren {-1}^m \paren {x_j \map {e_{m - 1} } {U_j} x_j^{k - m} + \map {e_m} {U_j} x_j^{k - m} } }\) by (5), where $U_j = X \setminus \set {x_j}$
\(\ds \leadsto \ \ \) \(\ds \) \(\) \(\ds \paren {-1}^{k - 1} \sum_{j \mathop = 1}^n \paren {\map {e_0} X x_j^k + \sum_{m \mathop = 1}^{k - 1} \paren {-1}^m \map {e_{m - 1} } {U_j} x_j^{k - m + 1} + \sum_{m \mathop = 1}^{k - 1} \paren {-1}^m \map {e_m} {U_j} {x_j^{k - m} } }\) adjust summations and collect powers of $x_j$
\(\text {(7)}: \quad\) \(\ds \leadsto \ \ \) \(\ds \) \(\) \(\ds \paren {-1}^{k - 1} \sum_{j \mathop = 1}^n \paren {-1}^{k - 1} x_j \map {e_k} {U_j}\) telescoping sum reduces to a single term



It remains to prove (7) matches (1):

\(\text {(8)}: \quad\) \(\ds \sum_{j \mathop = 1}^n x_j \map {e_k} {X \setminus \set {x_j} }\) \(=\) \(\ds k \map {e_k} X\) for $1 \le k \le n$

Define:

$\map {y_i} t = t\, x_i, 1 \le i \le n$
$X_t = \set {\map {y_1} t, \ldots, \map {y_n} t}$
$\map f t = \map {e_k} {tx_1, \ldots, tx_n}$.

Then there are two equations (9)-(10) for $\map {f'} t$:

\(\text {(9)}: \quad\) \(\ds \map {f'} t\) \(=\) \(\ds \sum_{j \mathop = 1}^n x_j \map {e_k} {X_t \setminus \set {\map {y_j} t} }\) chain rule for several variables
\(\text {(10)}: \quad\) \(\ds \map f t\) \(=\) \(\ds t^k \map {e_k} X\) because $f$ is a homogeneous function of degree $k$
\(\ds \leadsto \ \ \) \(\ds \map {f'} t\) \(=\) \(\ds k t^{k - 1} \map {e_k} X\) Power Rule for Derivatives

Let $t = 1$ in (9) and (10) to prove (8).

$\blacksquare$