Newton-Girard Formulas/Lemma 1

Theorem

Let $a, b \in \Z$ be integers such that $b \ge a$.

Let $U$ be a set of $n = b - a + 1$ numbers $\left\{ {x_a, x_{a + 1}, \ldots, x_b}\right\}$.

Let:

$\ds h_m$

$=$

$\ds \sum_{a \mathop \le j_1 \mathop < \cdots \mathop < j_m \mathop \le b} \left({\prod_{k \mathop = 1}^m x_{j_k} }\right)$

$\ds $

$=$

$\ds \sum_{a \mathop \le j_1 \mathop < \cdots \mathop < j_m \mathop \le b} x_{j_1} \cdots x_{j_m}$

That is, $h_m$ is the product of all $m$-tuples of elements of $U$ taken $m$ at a time, excluding repetitions.

Let $G \left({z}\right)$ be the generating function for the sequence $\left\langle{h_m}\right\rangle$.

Then:

$\ds G \left({z}\right)$

$=$

$\ds \prod_{k \mathop = a}^b \left({1 + x_k z}\right)$

$\ds $

$=$

$\ds \left({1 + x_a z}\right) \left({1 + x_{a + 1} z}\right) \cdots \left({1 + x_b z}\right)$

$\blacksquare$