Newton-Girard Formulas/Recurrence Formula

From ProofWiki
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

Retrieved from "https://proofwiki.org/w/index.php?title=Newton-Girard_Formulas/Recurrence_Formula&oldid=542556"