Generating Function for Elementary Symmetric Function/Proof 3

From ProofWiki
Jump to navigation Jump to search

Theorem

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

\(\ds \map {e_m} U\) \(=\) \(\ds \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} }\)
\(\ds \) \(=\) \(\ds \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}\)

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

We have by definition of generating function that:

$\map G z = \ds \sum_{n \mathop \ge 0} a_n z^n$

We have that:

$a_0 = 1$



Suppose $n = 1$.

Let $\map G z$ be the generating function for $\sequence {a_m}$ under this condition.

Then:

$1 \mathop \le j_1 \mathop < j_2 \mathop < \mathop \cdots \mathop < j_m \mathop \le 1$

can be fulfilled by only one set $\set {j_1, j_2, \ldots, j_m}$, that is:

$j_1 = 1$


Thus in this case:

\(\ds a_m\) \(=\) \(\ds x_1 \delta_{m 1}\) where $\delta_{m 1}$ is the Kronecker delta.
\(\ds \leadsto \ \ \) \(\ds \map G z\) \(=\) \(\ds \sum_{n \mathop \ge 0} x_1 \delta_{n 1} z^n\)
\(\ds \leadsto \ \ \) \(\ds \map G z\) \(=\) \(\ds 1 + x_1 z\)

Then by Product of Generating Functions, it follows that:

$\map G z = \paren {1 + x_1 z} \paren {1 + x_2 z} \cdots \paren {1 + x_n z}$