Summation of Products of n Numbers taken m at a time with Repetitions/Inverse Formula/Examples/Degree 3

From ProofWiki
Jump to navigation Jump to search

Example of Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula

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 $m \in \Z_{>0}$ be a (strictly) positive integer.


Let:

\(\displaystyle h_m\) \(=\) \(\displaystyle \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le j_m \mathop \le b} \left({\prod_{k \mathop = 1}^m x_{j_k} }\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le 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.


For $r \in \Z_{> 0}$, let:

$S_r = \displaystyle \sum_{j \mathop = a}^b {x_j}^r$


Then:

$S_3 = 3 h_3 - 3 h_1 h_2 + {h_1}^3$


Proof

From Summation of Products of n Numbers taken m at a time with Repetitions: Inverse Formula:

$S_m = \displaystyle \sum_{k_1 \mathop + 2 k_2 \mathop + \mathop \cdots \mathop + m k_m \mathop = m} \left({-1}\right)^{k_1 + k_2 + \cdots + k_m - 1} \dfrac {m \left({k_1 + k_2 + \cdots + k_m - 1}\right)! } {k_1! \, k_2! \, \cdots k_m!} {h_1}^{k_1} {h_2}^{k_2} \cdots {h_m}^{k_m}$

where:

$k_1 + 2 k_2 + \cdots + m k_m = m$


We need to find all sets of $k_1, k_2, k_3 \in \Z_{\ge 0}$ such that:

$k_1 + 2 k_2 + 3 k_3 = 3$

Thus $\left({k_1, k_2, k_3}\right)$ can be:

$\left({3, 0, 0}\right)$
$\left({1, 1, 0}\right)$
$\left({0, 0, 1}\right)$


Hence:

\(\displaystyle S_3\) \(=\) \(\displaystyle \left({-1}\right)^{3 + 0 + 0 - 1} \dfrac {3 \left({3 + 0 + 0 - 1}\right)! } {3! \, 0! \, 0!} {h_1}^3 {h_2}^0 {h_3}^0\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{1 + 1 + 0 - 1} \dfrac {3 \left({1 + 1 + 0 - 1}\right)! } {1! \, 1! \, 0!} {h_1}^1 {h_2}^1 {h_3}^0\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle \left({-1}\right)^{0 + 0 + 1 - 1} \dfrac {3 \left({0 + 0 + 1 - 1}\right)! } {0! \, 0! \, 1!} {h_1}^0 {h_2}^0 {h_3}^1\)
\(\displaystyle \) \(=\) \(\displaystyle \dfrac {3 \times 2 {h_1}^3} 6 - \dfrac {3 {h_1}^1 {h_2}^1} 1 + \dfrac {3 {h_3}^1} 1\)
\(\displaystyle \) \(=\) \(\displaystyle 3 h_3 - 3 h_1 h_2 + {h_1}^3\)

$\blacksquare$


Sources