Newton-Girard Formulas/Recurrence Formula
Jump to navigation
Jump to search
Theorem
Let $a, b \in \Z$ be integers such that $b \ge a$.
Let $U$ be a set of $n = b - a + 1$ numbers $\set {x_a, x_{a + 1}, \ldots, x_b}$.
Let $m \in \Z_{>0}$ be a (strictly) positive integer.
Let:
\(\ds h_m\) | \(=\) | \(\ds \sum_{a \mathop \le j_1 \mathop < \mathop \cdots \mathop < j_m \mathop \le b} \paren {\prod_{k \mathop = 1}^m x_{j_k} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{a \mathop \le j_1 \mathop < \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.
For $r \in \Z_{> 0}$, let:
- $S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$
A recurrence relation for $h_n$ can be given as:
\(\ds h_n\) | \(=\) | \(\ds \sum_{k \mathop = 1}^n \dfrac {\paren {-1}^{k + 1} S_k h_{n - k} } n\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac 1 n \paren {S_1 h_{n - 1} - S_2 h_{n - 2} + \cdots S_n h_0}\) |
for $n \ge 1$.
Proof
This theorem requires a proof. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code.If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page. |
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$