Summation of Product of Differences

Theorem

$\ds \sum_{1 \mathop \le i \mathop < j \mathop \le n} \paren {u_j - u_k} \paren {v_j - v_k} = n \sum_{j \mathop = 1}^n u_j v_j - \sum_{j \mathop = 1}^n u_j \sum_{j \mathop = 1}^n v_j$

Proof

Take the Binet-Cauchy Identity:

$\ds \paren {\sum_{i \mathop = 1}^n a_i c_i} \paren {\sum_{j \mathop = 1}^n b_j d_j} = \paren {\sum_{i \mathop = 1}^n a_i d_i} \paren {\sum_{j \mathop = 1}^n b_j c_j} + \sum_{1 \mathop \le i \mathop < j \mathop \le n} \paren {a_i b_j - a_j b_i} \paren {c_i d_j - c_j d_i}$

Make the following assignments:

\(\ds 1 \le i \le n: \, \)

\(\ds a_i\)

\(:=\)

\(\ds u_i\)

\(\ds 1 \le i \le n: \, \)

\(\ds c_i\)

\(:=\)

\(\ds v_i\)

\(\ds 1 \le j \le n: \, \)

\(\ds b_j\)

\(:=\)

\(\ds 1\)

\(\ds 1 \le j \le n: \, \)

\(\ds d_j\)

\(:=\)

\(\ds 1\)

Then we have:

$\ds \paren {\sum_{i \mathop = 1}^n u_i v_i} \paren {\sum_{j \mathop = 1}^n 1 \times 1} = \paren {\sum_{i \mathop = 1}^n u_i \times 1} \paren {\sum_{j \mathop = 1}^n 1 \times v_j} + \sum_{1 \mathop \le i \mathop < j \mathop \le n} \paren {u_i \times 1 - u_j \times 1} \paren {v_i \times 1 - v_j \times 1}$

and the result follows.

$\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: Exercise $31$