Elementary Symmetric Function/Examples/Recursion

From ProofWiki
Jump to navigation Jump to search

Example of Elementary Symmetric Function: Recursion

Let $\set {z_1, z_2, \ldots, z_{n+1}}$ be a set of $n+1$ values, duplicate values permitted.

Then for $1 \le m \le n$:

$\displaystyle e_m \paren { \set {z_1,\ldots,z_n,z_{n+1} } } = z_{n+1} e_{m-1} \paren { \set {z_1,\ldots,z_n} } + e_m \paren { \set {z_1,\ldots,z_n} } $

Proof

Case $m=1$ holds because $e_0$ is $1$ and $e_1$ is the sum of the elements.

Assume $2 \le m \le n$.

Define four sets:

$\displaystyle A = \set { \set {p_1,\ldots,p_m} : 1 \le p_1 \lt \cdots \lt p_m \le n+1}$
$\displaystyle B = \set { \set {p_1,\ldots,p_m} : 1 \le p_1 \lt \cdots \lt p_{m-1} \le n, p_m = n+1}$
$\displaystyle C = \set { \set {p_1,\ldots,p_{m}} : 1 \le p_1 \lt \cdots \lt p_{m} \le n}$
$\displaystyle D = \set { \set {p_1,\ldots,p_{m-1}} : 1 \le p_1 \lt \cdots \lt p_{m-1} \le n}$

Then $A = B \cup C$ and $B \cap C = \empty$ implies:

$\displaystyle \sum_{A} z_{p_1} \cdots z_{p_m} = \sum_{B} z_{p_1} \cdots z_{p_m} + \sum_{C} z_{p_1} \cdots z_{p_m}$

Simplify:

$\displaystyle \sum_{B} z_{p_1} \cdots z_{p_m} = z_{n+1} \sum_{D} z_{p_1} \cdots z_{p_{m-1}}$

Notation for Elementary Symmetric Functions:

$\displaystyle e_m \paren { \set {z_1,\ldots,z_n,z_{n+1} } } = \sum_{A} z_{p_1} \cdots z_{p_m} $
$\displaystyle \sum_{D} z_{p_1} \cdots z_{p_{m-1} } = e_{m-1} \paren { \set {z_1,\ldots,z_n} } $
$\displaystyle \sum_{C} z_{p_1} \cdots z_{p_m} = e_m \paren { \set {z_1,\ldots,z_n} } $

Assemble the preceding equations:

\(\displaystyle e_m \paren { \set {z_1,\ldots,z_n,z_{n+1} } }\) \(=\) \(\displaystyle \sum_{A} z_{p_1} \cdots z_{p_m}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{B} z_{p_1} \cdots z_{p_m} + \sum_{C} z_{p_1} \cdots z_{p_m}\)
\(\displaystyle \) \(=\) \(\displaystyle z_{n+1} \sum_{D} z_{p_1} \cdots z_{p_m} + \sum_{C} z_{p_1} \cdots z_{p_m}\)
\(\displaystyle \) \(=\) \(\displaystyle z_{n+1} e_{m-1} \paren { \set {z_1,\ldots,z_n} } + e_m \paren { \set {z_1,\ldots,z_n} }\)

$\blacksquare$