Summation of Products of n Numbers taken m at a time with Repetitions/Examples/Order 3/Proof 1

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

Retrieved from "https://proofwiki.org/w/index.php?title=Summation_of_Products_of_n_Numbers_taken_m_at_a_time_with_Repetitions/Examples/Order_3/Proof_1&oldid=361110"