# Generating Function for Elementary Symmetric Function

## Theorem

Let $U$ be a set of $n$ numbers $\set {x_1, x_2, \ldots, x_n}$.

Define:

\(\displaystyle \map {e_m} {U}\) | \(=\) | \(\displaystyle \begin{cases} 1 & m = 0\\ \displaystyle \sum_{1 \mathop \le j_1 \mathop < \mathop \cdots \mathop < j_m \mathop \le n} x_{j_1} x_{j_2} \cdots x_{j_m} & 1 \leq m \leq n \\ 0 & m \gt n \\ \end{cases}\) | elementary symmetric function | ||||||||||

\(\displaystyle a_m\) | \(=\) | \(\displaystyle \map {e_m} U\) | for $m=0,1,2,\ldots$ | ||||||||||

\(\displaystyle \map G z\) | \(=\) | \(\displaystyle \displaystyle \sum_{m=0}^\infty a_m z^m\) | generating function for $\set {a_m}_{m=0}^\infty$ |

Then:

\(\displaystyle \map G z\) | \(=\) | \(\displaystyle \displaystyle \prod_{k \mathop = 1}^n \paren {1 + x_k z}\) |

### Explanation

Generating function discovery methods can find a formula for $\map G z$.

Let $n=1$.

Then $U$ is a singleton set $\set {x_1}$.

Expand the formal series:

\(\displaystyle \map G z\) | \(=\) | \(\displaystyle \map {e_0} U + \map {e_1} z + \sum_{m=2}^\infty 0 z^m\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle 1 + x_1 z\) | Because $\map {e_0} U = 1$ and $\map {e_1} U = x_a$ |

Product of Generating Functions and experience with elementary symmetric functions suggests:

- $\displaystyle \map G z = \paren {1 + x_1 z} \paren {1 + x_{2} z} \cdots \paren {1 + x_n z}$

Knuth (1997) section 1.2.9 discusses the technique and the issue of a valid proof.

## Proof 1

The summation for $\map G z$ is a finite sum $m = 0, 1, \ldots, n$, which settles convergence issues.

Begin with Viete's Formulas:

- $\displaystyle \prod_{k \mathop = a}^b \paren {x - x_k} = x^n + \sum_{m \mathop = 0}^{n - 1} \paren {-1}^{n - m} \map {e_{n - m} } U \, x^m$

Change variables $x = -1 / z$:

\(\displaystyle \prod_{k \mathop = 1}^n \paren {-\frac 1 z - x_k}\) | \(=\) | \(\displaystyle \paren {-z}^{-n} + \sum_{m \mathop = 0}^{n - 1} \paren {-1}^{n - m} \map {e_{n - m} } U \, \paren {-z}^{-m}\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \prod_{k \mathop = 1}^n \paren {1 + x_k z}\) | \(=\) | \(\displaystyle z^n + \sum_{m \mathop = 0}^{n - 1} \map {e_{n - m} } U \, \paren z^{n - m}\) | all signs cancel | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \prod_{k \mathop = 1}^n \paren {1 + x_k z}\) | \(=\) | \(\displaystyle \sum_{m \mathop = 0}^n \map {e_m} U \, z^m\) |

$\blacksquare$

## Proof 2

Apply mathematical induction on $n$.

Let $\map P n$ be the statement that

\(\displaystyle \map G z\) | \(\equiv\) | \(\displaystyle \displaystyle \sum_{m \mathop = 0}^{n+1} \map {e_m} { \set {x_1,\ldots,x_n} } z^{m}\) | |||||||||||

\(\displaystyle \) | \(=\) | \(\displaystyle \displaystyle \prod_{k \mathop = 1}^n \paren {1+x_kz}\) |

Set $U = \set {x_1}$ for $n=1$.

Expand the formal series:

\(\displaystyle \map G z\) | \(=\) | \(\displaystyle \map {e_0} U + \map {e_1} {U} z + \displaystyle\sum_{m \mathop = 2}^\infty \map {e_m} {U} z^m\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \map {e_0} U + \map {e_1} {U} z\) | The summation has all zero terms. | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle 1 + x_1 z\) |

Then $\map P 1$ holds.

Assume $\map P n$ holds. Let's prove $\map P {n+1}$ holds.

The induction step uses a recursion relation:

\(\text {(1)}: \quad\) | \(\displaystyle e_m \paren { \set {x_1,\ldots,x_n,x_{n+1} } }\) | \(=\) | \(\displaystyle x_{n+1} e_{m-1} \paren { \set {x_1,\ldots,x_n} } + e_m \paren { \set {x_1,\ldots,x_n} }\) | Elementary Symmetric Function/Examples/Recursion |

Let $\map G z$ be defined by statement $\map P n$.

Let $\map {G^*} z$ be defined by statement $\map P {n+1}$.

Then:

\(\displaystyle \map {G^*} z\) | \(=\) | \(\displaystyle \displaystyle \prod_{k \mathop = 1}^{n+1} \paren {1+x_kz}\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \map G z \paren { 1 + x_{n+1} z }\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \map G z + x_{n+1} z \map G z\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \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}\) | use hypothesis $\map P n$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \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}\) | because $\map {e_{n+1} } {U} = 0$ | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \map {e_0} {U} + \sum_{m \mathop = 1}^{n+1} \map {e_m} {\set {x_1,\ldots,x_n,x_{n+1} } } z^{m}\) | by recursion relation (1) | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \) | \(=\) | \(\displaystyle \sum_{m \mathop = 0}^{n+1} \map {e_m} {\set {x_1,\ldots,x_n,x_{n+1} } } z^{m}\) | because $\map {e_0} {X} = 1$ for all sets $X$ |

Then $\map P {n+1}$ holds, completing the induction.

$\blacksquare$

## Proof 3

We have by definition of generating function that:

- $G \left({z}\right) = \displaystyle \sum_{n \mathop \ge 0} a_n z^n$

We have that:

- $a_0 = 1$

Suppose $n=1$.

Let $G \left({z}\right)$ be the generating function for $\left\langle{a_m}\right\rangle$ 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 $\left\{ {j_1, j_2, \ldots, j_m}\right\}$, that is:

- $j_1 = 1$

Thus in this case:

\(\displaystyle a_m\) | \(=\) | \(\displaystyle x_1 \delta_{m 1}\) | where $\delta_{m 1}$ is the Kronecker delta. | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle G \left({z}\right)\) | \(=\) | \(\displaystyle \sum_{n \mathop \ge 0} x_1 \delta_{n 1} z^n\) | ||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle G \left({z}\right)\) | \(=\) | \(\displaystyle 1 + x_1 z\) |

Then by Product of Generating Functions, it follows that:

- $G \left({z}\right) = \left({1 + x_1 z}\right) \left({1 + x_{2} z}\right) \cdots \left({1 + x_n z}\right)$

## Sources

- 1997: Donald E. Knuth:
*The Art of Computer Programming: Volume 1: Fundamental Algorithms*(3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions: Exercise $10$