# 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 \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 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$ $\ds \displaystyle \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$ 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$ $\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}$

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}$ symmetric function recursion, valid for $1 \le m \le p$.

The right 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 \displaystyle \sum_{j \mathop = 1}^n x_j \map {e_{k} } {X \setminus \set {x_j} }$ $=$ $\ds 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$ $\ds \map {f'} t$ $=$ $\ds \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$ $\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$ by calculus power rule

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

$\blacksquare$