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:

\(\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:

\(\text {(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$
\(\text {(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

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

Details

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

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

Create $n$ equations all with left 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\) \(\displaystyle 0\) \(=\) \(\displaystyle \sum_{j \mathop = 1}^n \sum_{i \mathop = 0}^n \paren {-1}^{n-i} {\map {e_{n-i} } X} { x_j^{ i+r } }\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 0}^n \paren {-1}^{n-i} {\map {e_{n-i} } X} {\map {p_{i+r} } X}\)

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\) \(\displaystyle \map {e_{m} } {z_1,\ldots,z_p,z_{p+1} }\) \(=\) \(\displaystyle z_{p+1} \map {e_{m-1} } {z_1,\ldots,z_p} + \map {e_m} {z_1,\ldots,z_p}\) symmetric function recursion, valid for $1 \le m \le p$.

The right side of (1) is:

\(\text {(6)}: \quad\) \(\displaystyle \) \(\) \(\displaystyle \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.
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(\) \(\displaystyle \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$.
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(\) \(\displaystyle \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}$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(\) \(\displaystyle \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\) \(\displaystyle \leadsto \ \ \) \(\displaystyle \) \(\) \(\displaystyle \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\) \(\displaystyle \displaystyle \sum_{j \mathop = 1}^n x_j \map {e_{k} } {X \setminus \set {x_j} }\) \(=\) \(\displaystyle k \, \map {e_k} X\) for $1 \leq k \leq 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\) \(\displaystyle \map {f'} t\) \(=\) \(\displaystyle \displaystyle \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\) \(\displaystyle \map f t\) \(=\) \(\displaystyle t^k \map {e_k} X\) because $f$ is a homogeneous function of degree $k$
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map {f'} t\) \(=\) \(\displaystyle k t^{k-1} \map {e_k} X\) by calculus power rule

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

$\blacksquare$