# Newton's Identities/Proof 1

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

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