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

Jump to navigation
Jump to search

## Theorem

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

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}\) | Change of Index Variable of Summation |

The result follows on multiplying by $\dfrac 1 2$.

$\blacksquare$

## 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: Example $2$. $(13)$