Theorem: Generating Function for Elementary Symmetric Function

Let $U$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.
Let $\map {e_m} U$ be the elementary symmetric function of degree $m$ on $U$:
{{begin-eqn}}
{{eqn | l = \map {e_m} U
      | r = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} \paren {\prod_{i \mathop = 1}^m x_{j_i} }
      | c = 
}}
{{eqn | r = \sum_{1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} x_{j_1} x_{j_2} \cdots x_{j_m}
      | c = 
}}
{{end-eqn}}
Let $a_m := \map {e_m} U$ for $m = 0, 1, 2, \ldots$
Let $\map G z$ be a generating function for the sequence $\sequence {a_m}$:
:$\ds \map G z = \sum_{m \mathop = 0}^\infty a_m z^m$
Then:
:$\ds \map G z = \prod_{k \mathop = 1}^n \paren {1 + x_k z}$

Proof:
Apply mathematical induction on $n$.
Let $\map P n$ be the statement:
{{begin-eqn}}
{{eqn | l = \map G z
      | o = \equiv
      | r = \sum_{m \mathop = 0}^{n + 1} \map {e_m} {\set {x_1, \ldots, x_n} } z^m
}}
{{eqn | r = \prod_{k \mathop = 1}^n \paren {1 + x_k z}
}}
{{end-eqn}}
Basis for the induction:
Set $U = \set {x_1}$ for $n = 1$.
Expand the formal series:
{{begin-eqn}}
{{eqn | l = \map G z 
      | r = \map {e_0} U + \map {e_1} U z + \sum_{m \mathop = 2}^\infty \map {e_m} U z^m
}}
{{eqn | ll = \leadsto
      | r = \map {e_0} U + \map {e_1} U z 
      | c = as the summation has all zero terms
}}
{{eqn | ll = \leadsto
      | r = 1 + x_1 z
}}
{{end-eqn}}
Then $\map P 1$ holds.
Induction step:
Assume $\map P n$ holds.
Let's prove $\map P {n + 1}$ holds.
{{improve|Let's rewrite this so it's not in kindergarten language.}}
The induction step uses a recursion relation:
{{begin-eqn}}
{{eqn | n = 1
      | l = \map {e_m} {\set {x_1, \ldots, x_n, x_{n + 1} } } 
      | r = x_{n + 1} \map {e_{m - 1} } {\set {x_1, \ldots, x_n} } + \map {e_m} {\set {x_1, \ldots, x_n} }
      | c = Recursion Property of Elementary Symmetric Function
}}
{{end-eqn}}
Let $\map G z$ be defined by statement $\map P n$.
Let $\map {G^*} z$ be defined by statement $\map P {n + 1}$.
Then:
{{begin-eqn}}
{{eqn | l = \map {G^*} z 
      | r = \prod_{k \mathop = 1}^{n + 1} \paren {1 + x_k z}
}}
{{eqn | ll= \leadsto
      | r = \map G z \paren {1 + x_{n + 1} z}
}}
{{eqn | ll= \leadsto
      | r = \map G z + x_{n + 1} z \map G z
}}
{{eqn | ll= \leadsto
      | r = \sum_{m \mathop = 0}^n \map {e_m} U z^m + \sum_{m \mathop = 1}^{n+1} x_{n+1} \map {e_{m-1} } U z^m
      | c = use hypothesis $\map P n$
}}
{{eqn | ll= \leadsto
      | r = \map {e_0} U + \sum_{m \mathop = 1}^{n + 1} \paren {\map {e_m} U + x_{n + 1} \map {e_{m - 1} } U} z^m
      | c = because $\map {e_{n+1} } {U} = 0$
}}
{{eqn | ll= \leadsto
      | r = \map {e_0} U + \sum_{m \mathop = 1}^{n + 1} \map {e_m} {\set {x_1, \ldots, x_n, x_{n + 1} } } z^m
      | c = by recursion relation $(1)$
}}
{{eqn | ll= \leadsto
      | r = \sum_{m \mathop = 0}^{n + 1} \map {e_m} {\set {x_1, \ldots, x_n, x_{n + 1} } } z^m
      | c = because $\map {e_0} X = 1$ for all sets $X$
}}
{{end-eqn}}
Then $\map P {n + 1}$ holds, completing the induction.
{{Mistake|The indices on the summation are inconsistent with the statement of $\map P n$}}
{{qed}}