Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 3/Proof 1
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k = \dfrac { {S_1}^3} 6 + \dfrac {S_1 S_2} 2 + \dfrac {S_3} 3$
where:
- $\ds S_r := \sum_{k \mathop = a}^b {x_k}^r$
Proof
Let:
\(\text {(a)}: \quad\) | \(\ds A\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k\) | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{a \mathop \le i \mathop \le j \mathop \le k \mathop \le b} x_i x_j x_k\) | ||||||||||||
\(\text {(b)}: \quad\) | \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = j}^b x_i x_j x_k\) | |||||||||||
\(\text {(c)}: \quad\) | \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^j x_i x_j x_k\) | |||||||||||
\(\text {(d)}: \quad\) | \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = i}^j x_i x_j x_k\) | |||||||||||
\(\text {(e)}: \quad\) | \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = i}^b x_i x_j x_k\) |
Also, let:
\(\ds S_1\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b x_i\) | ||||||||||||
\(\ds S_2\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b {x_i}^2\) | ||||||||||||
\(\ds S_3\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b {x_i}^3\) |
Hence:
\(\ds 2 A\) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = j}^b x_i x_j x_k + \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^j x_i x_j x_k\) | $(b) + (c)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \left({\sum_{k \mathop = j}^b x_i x_j x_k + \sum_{k \mathop = i}^j x_i x_j x_k}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \left({\sum_{k \mathop = i}^b x_i x_j x_k + x_i x_j x_j}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b x_j}\right)^2 + \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b {x_j}^2}\right)\) |
Let:
\(\ds A_1\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b x_j}\right)^2\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b x_i \sum_{j \mathop = i}^b x_j \sum_{k \mathop = i}^b x_k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^b x_i x_j x_k\) | ||||||||||||
\(\ds A_3\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b {x_j}^2}\right)\) |
as calculated above.
Thus:
- $(1): \quad 2 A = A_1 + A_3$
Similarly:
\(\ds 2 A\) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k + \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = j}^i x_i x_j x_k\) | $(a) + (d)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \left({\sum_{k \mathop = a}^j x_i x_j x_k + \sum_{k \mathop = j}^i x_i x_j x_k}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \left({\sum_{k \mathop = a}^i x_i x_j x_k + x_i x_j x_j}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = a}^i x_j}\right)^2 + \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = a}^i {x_j}^2}\right)\) |
Then:
\(\ds A_1 + A\) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^b x_i x_j x_k + \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = i}^b x_i x_j x_k\) | using $(e)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{k \mathop = i}^b \left({\sum_{j \mathop = i}^b x_i x_j x_k + \sum_{j \mathop = a}^i x_i x_j x_k}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{k \mathop = i}^b \left({\sum_{j \mathop = a}^b x_i x_j x_k + {x_i}^2 x_k}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b x_i \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_j x_k + \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b {x_i}^2 x_j\) |
Let:
\(\ds A_2\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b x_i \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_j x_k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_i x_j x_k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = a}^j x_i x_j x_k\) | ||||||||||||
\(\ds A_4\) | \(:=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b {x_i}^2 x_j\) |
as calculated above.
Thus:
- $(2): \quad A_1 + A = A_2 + A_4$
Then:
\(\ds 2 A_2\) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_i x_j x_k + \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = a}^j x_i x_j x_k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \left({\sum_{k \mathop = j}^b x_i x_j x_k + \sum_{k \mathop = a}^j x_i x_j x_k}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \left({\sum_{k \mathop = a}^b x_i x_j x_k + x_i {x_j}^2}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \left({\sum_{i \mathop = a}^b x_i}\right)^3 + \sum_{i \mathop = a}^b x_i \sum_{i \mathop = a}^b {x_i}^2\) | ||||||||||||
\(\text {(3)}: \quad\) | \(\ds \) | \(=\) | \(\ds {S_1}^3 + S_1 S_2\) |
Now we have that:
\(\ds A_3\) | \(=\) | \(\ds \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b {x_j}^2}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b {x_i}^2 \left({\sum_{j \mathop = a}^i x_j}\right)\) |
and so:
\(\ds A_3 + A_4\) | \(=\) | \(\ds \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i {x_i}^2 x_j + \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b {x_i}^2 x_j\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b \left({\sum_{j \mathop = a}^b {x_i}^2 x_j + {x_i}^3}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{i \mathop = a}^b {x_i}^2 \sum_{i \mathop = a}^b x_i + \sum_{i \mathop = a}^b {x_i}^3\) | ||||||||||||
\(\text {(4)}: \quad\) | \(\ds \) | \(=\) | \(\ds S_2 S_1 + S_3\) |
Finally:
\(\ds 2 A\) | \(=\) | \(\ds A_1 + A_3\) | from $(1)$ | |||||||||||
\(\ds A + A_1\) | \(=\) | \(\ds A_2 + A_4\) | from $(2)$ | |||||||||||
\(\ds 2 A_2\) | \(=\) | \(\ds {S_1}^3 + S_1 S_2\) | from $(3)$ | |||||||||||
\(\ds A_3 + A_4\) | \(=\) | \(\ds S_1 S_2 + S_3\) | from $(4)$ | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 3 A + A_1\) | \(=\) | \(\ds A_1 + A_2 + A_3 + A_4\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 3 A\) | \(=\) | \(\ds A_2 + A_3 + A_4\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds 6 A\) | \(=\) | \(\ds 2 A_2 + 2 \left({A_3 + A_4}\right)\) | |||||||||||
\(\ds \) | \(=\) | \(\ds {S_1}^3 + S_1 S_2 + 2 S_1 S_2 + 2 S_3\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds {S_1}^3 + 3 S_1 S_2 + 2 S_3\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds A\) | \(=\) | \(\ds \frac { {S_1}^3} 6 + \frac {S_1 S_2} 2 + \frac {S_3} 3\) |
$\blacksquare$
This article needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code.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 {{Proofread}} from the code. |
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.3$: Sums and Products: Exercise $29$