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

From ProofWiki
Jump to: navigation, search

Theorem

$\displaystyle \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:

$\displaystyle S_r := \sum_{k \mathop = a}^b {x_k}^r$


Proof

Let:

\((a):\quad\) \(\displaystyle A\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = a}^j x_i x_j x_k\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{a \mathop \le i \mathop \le j \mathop \le k \mathop \le b} x_i x_j x_k\) $\quad$ $\quad$
\((b):\quad\) \(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = j}^b x_i x_j x_k\) $\quad$ $\quad$
\((c):\quad\) \(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^j x_i x_j x_k\) $\quad$ $\quad$
\((d):\quad\) \(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = i}^j x_i x_j x_k\) $\quad$ $\quad$
\((e):\quad\) \(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^i \sum_{k \mathop = i}^b x_i x_j x_k\) $\quad$ $\quad$


Also, let:

\(\displaystyle S_1\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b x_i\) $\quad$ $\quad$
\(\displaystyle S_2\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b {x_i}^2\) $\quad$ $\quad$
\(\displaystyle S_3\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b {x_i}^3\) $\quad$ $\quad$


Hence:

\(\displaystyle 2 A\) \(=\) \(\displaystyle \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\) $\quad$ $(b) + (c)$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$


Let:

\(\displaystyle A_1\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b x_j}\right)^2\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b x_i \sum_{j \mathop = i}^b x_j \sum_{k \mathop = i}^b x_k\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^b x_i x_j x_k\) $\quad$ $\quad$
\(\displaystyle A_3\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b {x_j}^2}\right)\) $\quad$ $\quad$

as calculated above.

Thus:

$(1): \quad 2 A = A_1 + A_3$


Similarly:

\(\displaystyle 2 A\) \(=\) \(\displaystyle \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\) $\quad$ $(a) + (d)$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$


Then:

\(\displaystyle A_1 + A\) \(=\) \(\displaystyle \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\) $\quad$ using $(e)$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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\) $\quad$ $\quad$


Let:

\(\displaystyle A_2\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b x_i \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_j x_k\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_i x_j x_k\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = a}^j x_i x_j x_k\) $\quad$ $\quad$
\(\displaystyle A_4\) \(:=\) \(\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b {x_i}^2 x_j\) $\quad$ $\quad$

as calculated above.

Thus:

$(2): \quad A_1 + A = A_2 + A_4$


Then:

\(\displaystyle 2 A_2\) \(=\) \(\displaystyle \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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \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\) $\quad$ $\quad$
\((3):\quad\) \(\displaystyle \) \(=\) \(\displaystyle {S_1}^3 + S_1 S_2\) $\quad$ $\quad$


Now we have that:

\(\displaystyle A_3\) \(=\) \(\displaystyle \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b {x_j}^2}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b {x_i}^2 \left({\sum_{j \mathop = a}^i x_j}\right)\) $\quad$ $\quad$


and so:

\(\displaystyle A_3 + A_4\) \(=\) \(\displaystyle \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\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b \left({\sum_{j \mathop = a}^b {x_i}^2 x_j + {x_i}^3}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = a}^b {x_i}^2 \sum_{i \mathop = a}^b x_i + \sum_{i \mathop = a}^b {x_i}^3\) $\quad$ $\quad$
\((4):\quad\) \(\displaystyle \) \(=\) \(\displaystyle S_2 S_1 + S_3\) $\quad$ $\quad$


Finally:

\(\displaystyle 2 A\) \(=\) \(\displaystyle A_1 + A_3\) $\quad$ from $(1)$ $\quad$
\(\displaystyle A + A_1\) \(=\) \(\displaystyle A_2 + A_4\) $\quad$ from $(2)$ $\quad$
\(\displaystyle 2 A_2\) \(=\) \(\displaystyle {S_1}^3 + S_1 S_2\) $\quad$ from $(3)$ $\quad$
\(\displaystyle A_3 + A_4\) \(=\) \(\displaystyle S_1 S_2 + S_3\) $\quad$ from $(4)$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3 A + A_1\) \(=\) \(\displaystyle A_1 + A_2 + A_3 + A_4\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle 3 A\) \(=\) \(\displaystyle A_2 + A_3 + A_4\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle 6 A\) \(=\) \(\displaystyle 2 A_2 + 2 \left({A_3 + A_4}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle {S_1}^3 + S_1 S_2 + 2 S_1 S_2 + 2 S_3\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle {S_1}^3 + 3 S_1 S_2 + 2 S_3\) $\quad$ $\quad$
\(\displaystyle \leadsto \ \ \) \(\displaystyle A\) \(=\) \(\displaystyle \frac { {S_1}^3} 6 + \frac {S_1 S_2} 2 + \frac {S_3} 3\) $\quad$ $\quad$

$\blacksquare$

Sources