Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 2
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}, \dotsc, x_b}$.
Then:
- $\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j = \dfrac 1 2 \paren {\paren {\sum_{i \mathop = a}^b x_i}^2 + \paren {\sum_{i \mathop = a}^b {x_i}^2} }$
Proof 1
Let:
\(\ds S_1\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{j \mathop = a}^b \sum_{i \mathop = j}^b x_i x_j\) | Summation of i from 1 to n of Summation of j from 1 to i | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b x_i x_j\) | Change of Index Variable of Summation | |||||||||||
\(\ds \) | \(=:\) | \(\ds S_2\) |
Then:
\(\ds 2 S_1\) | \(=\) | \(\ds S_1 + S_2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \paren {\sum_{j \mathop = a}^i x_i x_j + \sum_{j \mathop = i}^b x_i x_j}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \paren {\paren {\sum_{j \mathop = a}^b x_i x_j} + x_i x_i}\) | Sum of Summations over Overlapping Domains: Example | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b x_i x_j + \sum_{i \mathop = a}^b x_i x_i\) | Sum of Summations equals Summation of Sum | |||||||||||
\(\ds \) | \(=\) | \(\ds \paren {\sum_{i \mathop = a}^b x_i} \paren {\sum_{j \mathop = a}^b x_j} + \paren {\sum_{i \mathop = a}^b {x_i}^2}\) | General Distributivity Theorem and Change of Index Variable of Summation |
The result follows on multiplying by $\dfrac 1 2$.
$\blacksquare$
Proof 2
We have that:
- $\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i x_i x_j = \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le b} x_{j_1} x_{j_2}$
From Summation of Products of n Numbers taken m at a time with Repetitions:
- $\ds \sum_{a \mathop \le j_1 \mathop \le \cdots \mathop \le j_m \mathop \le b} x_{j_1} \cdots x_{j_m} = \sum_{\substack {k_1, k_2, \ldots, k_m \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop + \cdots \mathop + m k_m \mathop = m} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !} \cdots \dfrac { {S_m}^{k_m} } {m^{k_m} k_m !}$
where:
- $S_r = \ds \sum_{k \mathop = a}^b {x_k}^r$ for $r \in \Z_{\ge 0}$.
Setting $m = 2$:
\(\ds \sum_{a \mathop \le j_1 \mathop \le j_2 \mathop \le b} x_{j_1} x_{j_2}\) | \(=\) | \(\ds \sum_{\substack {k_1, k_2 \mathop \ge 0 \\ k_1 \mathop + 2 k_2 \mathop = 2} } \dfrac { {S_1}^{k_1} } {1^{k_1} k_1 !} \dfrac { {S_2}^{k_2} } {2^{k_2} k_2 !}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \dfrac { {S_1}^2 {S_2}^0} {\paren {1^2 \times 2!} \paren {2^0 \times 0!} } + \dfrac { {S_1}^0 {S_2}^1} {\paren {1^0 \times 0!} \paren {2^1 \times 1!} }\) | as $k_1 = 2, k_2 = 0$ and $k_1 = 0, k_2 = 1$ are the only $k_1$ and $k_2$ to fulfil the criteria | |||||||||||
\(\ds \) | \(=\) | \(\ds \frac 1 2 \paren { {S_1}^2 + S_2}\) | simplifying |
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.9$: Generating Functions