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

## 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$ $\displaystyle$ $=$ $\displaystyle \sum_{a \mathop \le i \mathop \le j \mathop \le k \mathop \le b} x_i x_j x_k$ $(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$ $(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$ $(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$ $(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$

Also, let:

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

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$ $(b) + (c)$ $\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)$ $\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)$ $\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)$

Let:

 $\displaystyle A_1$ $:=$ $\displaystyle \sum_{i \mathop = a}^b x_i \left({\sum_{j \mathop = i}^b x_j}\right)^2$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = a}^b x_i \sum_{j \mathop = i}^b x_j \sum_{k \mathop = i}^b x_k$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = i}^b \sum_{k \mathop = i}^b x_i x_j x_k$ $\displaystyle A_3$ $:=$ $\displaystyle \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:

 $\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$ $(a) + (d)$ $\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)$ $\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)$ $\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)$

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$ using $(e)$ $\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)$ $\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)$ $\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$

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$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = j}^b x_i x_j x_k$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = a}^b \sum_{j \mathop = a}^b \sum_{k \mathop = a}^j x_i x_j x_k$ $\displaystyle A_4$ $:=$ $\displaystyle \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:

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

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)$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = a}^b {x_i}^2 \left({\sum_{j \mathop = a}^i x_j}\right)$

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

Finally:

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

$\blacksquare$