Theorem: Newton-Girard Identities

Let $X$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.
Define:
{{begin-eqn}}
{{eqn | l = \mathbf S_m 
      | r = \set {\paren {j_1, \ldots, j_m} : 1 \le j_1 < \cdots < j_m \le n}
      | c = $1 \le m \le n$
}}
{{eqn | l = \map {e_m} X
      | r = \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}
      | c = {{Defof|Elementary Symmetric Function}}
}}
{{eqn | l = \map {p_k} X
      | r = \begin{cases} n & : k = 0 \\ \ds \sum_{i \mathop = 1}^n  x_i^k & : k \ge 1 \end {cases}
      | c = {{Defof|Power Sum}}
}}
{{end-eqn}}
The '''Newton-Girard Identities''' are:
{{begin-eqn}}
{{eqn | n = 1
      | l = k \map {e_k} X
      | r = \sum_{i \mathop = 1}^k \paren {-1}^{i - 1} \map {e_{k - i} } X \map {p_i} X
      | c = for $1 \le k \le n$
}}
{{eqn | n = 2
      | l = 0
      | r = \sum_{i \mathop = k - n}^k \paren {-1}^{i - 1} \map {e_{k - i} } X \map {p_i} X
      | c = for $1 \le n < k$
}}
{{end-eqn}}

Proof:
=== Outline ===
Calculus is used to prove identities (1) and (2) in a single effort. 
The tools are Viète's Formulas, the calculus derivative of powers $x^n$ and logarithm $\ln \size x$, Maclaurin series expansion coefficients, mathematical induction, and Leibniz's Rule in One Variable.
=== Lemma 1 ===
{{begin-eqn}}
{{eqn | l = \prod_{r \mathop = 1}^n  \paren {1 + x_r z}
      | r = \sum_{m \mathop = 0}^n {\map {e_m} X} z^m
}}
{{end-eqn}}
'''Proof of Lemma 1'''
Begin with:
{{begin-eqn}}
{{eqn | n = 11
      | l = \prod_{r \mathop = 1}^n  \paren {x - x_r} 
      | r = \sum_{i \mathop = 0}^n \paren {-1}^{n - i} {\map {e_{n - i} } X} x^i
      | c = Viète's Formulas
}}
{{end-eqn}}
Change variables in $(11)$: 
:$x = -1/z$
Details: Generating Function for Elementary Symmetric Function.
{{qed|lemma}}
=== Lemma 2 ===
Denote by $D^k \map f z$ the $k$th derivative of $\map f z$.
Let:
{{begin-eqn}}
{{eqn | l = \map G z 
      | r = \prod_{k \mathop = 1}^n \paren {1 + x_k z}
      | c = as in Lemma 1
}}
{{eqn | l = \map F z 
      | r = \dfrac {\map {DQ} z} {\map Q z}
      | c = the calculus derivative of $\ln \size {\map Q z}$
}}
{{end-eqn}}
Then:
{{begin-eqn}}
{{eqn | n = 12
      | l = \dfrac {D^m \map G 0} {m!} 
      | r = \map {e_m } X
}}
{{eqn | n = 13
      | l = \dfrac {D^m \map F 0} {m!} 
      | r = \paren {-1}^m \map {p_{m + 1} } X
}}
{{end-eqn}}
'''Proof of Lemma 2'''
{{begin-eqn}}
{{eqn | l = \map G z
      | r = \sum_{m \mathop = 0}^n {\map {e_m} X} z^m
      | c = by Lemma 1
}}
{{end-eqn}}
Then identity $(12)$ holds by Maclaurin series expansion applied to polynomial $G$.
Identity $(13)$ will be proved after mathematical induction establishes $(14)$ ''infra''. 
Let $\map {\mathbf P} m$ be the statement:
{{begin-eqn}}
{{eqn | n = 14
      | l = D^m \map F z 
      | r = \sum_{i \mathop = 1}^n \dfrac{ m!\paren {-1}^m  x_i^{m+1} }{ \paren { 1 + x_i z }^{m+1} }
      | c = for $m \ge 0$
}}
{{end-eqn}}
Basis for the induction: $m=0$
By calculus and the definition of $G$:
{{begin-eqn}}
{{eqn | l = \map F z 
      | r = \dfrac { D \map Q z}{\map Q z}
}}
{{eqn | ll= \leadsto 
      | r = \sum_{i \mathop = 1}^n \dfrac { x_i }{ 1 + x_i z }
}}
{{end-eqn}}
Then $\map {\mathbf P} 0$ is true.
Induction step $\map {\mathbf P} m$ implies $\map {\mathbf P} {m+1}$:
{{begin-eqn}}
{{eqn | l = D^{m + 1} \map F z 
      | r = \map D {\sum_{i \mathop = 1}^n \dfrac {m! \paren {-1}^m  x_i^{m + 1} } {\paren {1 + x_i z}^{m + 1} } }
      | c = by induction hypothesis $\map {\mathbf P} m$
}}
{{eqn | r = \sum_{i \mathop = 1}^n \dfrac{ m! \paren {-1}^m x_i^{m + 1} \paren {-1} \paren {m + 1} x_i} {\paren {1 + x_i z}^{m + 2} }
      | c = Power Rule for Derivatives: $\dfrac {\d u^{-n} } {\d z } = \paren {-n} u^{-n - 1} \dfrac {\d u} {\d z}$
}}
{{end-eqn}}
Simplify to prove $\map {\mathbf P} {m + 1}$ is true. 
The induction is complete.
To prove equation (13), first let $z = 0$ in equation (14). 
Divide by $m!$ to isolate $\map {p_{m + 1} } X$, which proves (13).
{{qed|lemma}}
=== Lemma 3 ===
{{begin-eqn}}
{{eqn | n = 15
      | l = \paren {m + 1} \map {e_{m + 1} } X 
      | r = \sum_{r \mathop = 0}^m \paren {-1}^r {\map {e_{m - r} } X} {\map {p_{r + 1} } X}
      | c = for $m \ge 0$
}}
{{end-eqn}}
'''Proof of Lemma 3'''
Begin with $D \map G z = {\map F z} {\map G z}$ and differentiate $m$ times on variable $z$:
{{begin-eqn}}
{{eqn | l = D^{m + 1} \map G z 
      | r = \sum_{r \mathop = 0}^m {\dbinom m r} D^r {\map F z} D^{m - r} {\map G z}
      | c = Leibniz's Rule in One Variable
}}
{{eqn | l = D^{m + 1} {\map G 0} 
      | r = \sum_{r \mathop = 0}^m \dbinom m r r! \paren {-1}^r {\map {p_{r + 1} } X} \paren {m - r}! \map {e_{m-r} } X
      | c = Evaluate at $ z = 0$ and use equations (12) and (13) in Lemma 2
}}
{{eqn | l = \paren {m + 1} {\map {e_m} X} 
      | r = \sum_{r \mathop = 0}^m  \paren {-1}^r {\map {e_{m-r} } X} {\map {p_{r+1} } X} 
      | c = Use (12), then collect factorials and simplify
}}
{{end-eqn}}
{{qed|lemma}}
'''Proof of the Theorem'''
To prove (1), start with equation (15) in Lemma 3.
Change indices via equations $m + 1 = k$, $r + 1 = i$. 
The summation is from $i = 0 + 1$ to $i = m + 1$, which gives range $i = 1$ to $k$. 
Subscript $m - r$ equals $k - 1- i + 1$, which simplifies to $k - i$.
Then:
{{begin-eqn}}
{{eqn | n = 16
      | l = k \map {e_k} X
      | r = \sum_{i \mathop = 1}^{k} \paren {-1}^{i - 1} {\map {e_{k - i} } X} {\map {p_i} X}
      | c = for $k \ge 1$, which is equation (1)
}}
{{end-eqn}}
To prove (2), assume $k > n \ge 1$ and $X = \set {x_1, \ldots, x_n}$.
Equation (16) implies:
{{begin-eqn}}
{{eqn | n = 17
      | l = 0
      | r = k \map {e_{k} } X
      | c = because $ \map {e_j} X = 0$ for $j = n + 1, \ldots, k$.
}}
{{eqn | ll= \leadsto
      | l = 0
      | r = \sum_{i \mathop = 1}^k \paren {-1}^{i - 1} {\map {e_{k - i} } X} {\map {p_i} X}
      | c = by (16) for $k \ge 1$
}}
{{eqn | ll= \leadsto
      | l = 0
      | r = \sum_{i \mathop = k - n}^k \paren {-1}^{i - 1} {\map {e_{k - i} } X} {\map {p_i} X}
      | c = because $ \map {e_{k - i} } X = 0$ when $n + 1 \le k - i \le k$
}}
{{end-eqn}}
Then (2) holds.
{{qed}}