They didn’t just interchange the index variables in that first example: they exploited the fact that doing so does not change the sum. Thus, they were able to write

$$2S=\sum_{1\le j<k\le n}(a_k-a_j)(b_k-b_j)+\sum_{1\le k<j\le n}(a_j-a_k)(b_j-b_k)\;,$$

getting a sum in which every possible term of the form $(a_i-a_\ell)(b_i-b_\ell)$ with $1\le i,\ell\le n$ appears **except** those in which $i=\ell$.

It may help to think of this in matrix terms. For $1\le j,k\le n$ let $c_{j,k}=(a_k-a_j)(b_k-b_j)$, and let

$$C=\begin{bmatrix}c_{1,1}&\color{red}{c_{1,2}}&\color{red}{\ldots}&\color{red}{c_{1,n-1}}&\color{red}{c_{1,n}}\\
\color{blue}{c_{2,1}}&c_{2,2}&\color{red}{\ldots}&\color{red}{c_{2,n-1}}&\color{red}{c_{2,n}}\\
\color{blue}{\vdots}&\color{blue}{\vdots}&\ddots&\color{red}{\vdots}&\color{red}{\vdots}\\
\color{blue}{c_{n-1,1}}&\color{blue}{c_{n-1,2}}&\color{blue}{\ldots}&c_{n-1,n-1}&\color{red}{c_{n-1,n}}\\
\color{blue}{c_{n,1}}&\color{blue}{c_{n,2}}&\color{blue}{\ldots}&\color{blue}{c_{n,n-1}}&c_{n,n}
\end{bmatrix}\;;$$

then $S$ is the sum of the (red) entries above the main diagonal of $C$, and the sum with the indices interchanged is the sum of the (blue) entries below the main diagonal of $C$. In this very special case the matrix $C$ happens to be symmetric, so the two sums are equal. Nicer yet, the entries on the main diagonal are all $0$, so the sum of all the entries in $C$ is $2S$. Thus, $2S$ is just the sum of all possible products of the form $(a_k-a_j)(b_k-b_j)$ with $1\le j,k\le n$, which is very easy to compute after we rewrite $(a_k-a_j)(b_k-b_j)$ as $a_kb_k-a_kb_j-a_jb_k+a_jb_j$.

What makes this work is the symmetry of the matrix $C$: this is one of the ‘important special cases’ mentioned in the sentence in the middle of page $36$. Learning to recognize them is to a great extent a matter of experience. In general, though, the first thing to do is see whether you can simply evaluate the summations in order as they’re written; if that doesn’t look promising, the next step is to see whether you can reverse the order of summation and get something nicer. Neither of these approaches looks very attractive in the problem above, so at that point you look for some other idea. Recognizing that a summation over $1\le j<k\le n$ or $1\le j\le k\le n$ is a summation over the upper half (give or take the diagonal) of an $n\times n$ matrix, you can reasonably look to see whether the whole matrix would be easier to work with and whether there’s an exploitable relationship between the upper and lower halves. Here both of those turn out to be the case.

## Best Answer

Suppose we have arrived at the expression $$6{n+1 \choose 4} + 6{n+1 \choose 3} + {n+1 \choose 2},$$ and we remain in a combinatorial mood, not an algebraic one. Then we might work a little harder and give a bijective argument.

From a group of $n+1$ boys and $n+1$ girls, we can choose $2$ boys and $2$ girls (a pair of pairs) in $$\binom{n+1}{2}^2$$ ways. We will count the number of pairs of pairs in another way.

Let the boys be called $b_0,b_1,\dots,b_n$, and the girls $g_0, g_1,\dots,g_n$. If $2$ boys and $2$ girls are chosen they either (a) share no number or (b) share $1$ number or (c) share $2$ numbers.

(a) The pairs of pairs that share no number can be chosen as follows.

Choose$4$ numbers from the set $\{0,1,\dots,n\}$. Then choose $2$ of the $4$ numbers, and select the boys with these $2$ numbers, and the girls with the remaining $2$ numbers. The choosing of $4$ numbers can be done in $\binom{n+1}{4}$ ways, and the choosing of $2$ from $4$ can be done in $\binom{4}{2}=6$ ways, for a total of $$6\binom{n+1}{4}.$$(b) The pairs of pairs that share exactly one number can be chosen as follows.

Choose$3$ numbers from $\{0,1,\dots,n\}$. Choose $1$ of these $3$ numbers to be the "duplicated" number (boy and girl), then select the boy who has $1$ of the remaining numbers, and the girl with the other. The choosing of the $3$ numbers can be done in $\binom{n+1}{3}$ ways. For each of these, we can choose the duplicated number in $3$ ways, and decide which of the remaining numbers will be a boy number in $2$ ways, for a total of $$(3)(2)\binom{n+1}{3}.$$(c) Finally, we count the pairs of pairs that share two numbers. All we need to do is to

choosethese $2$ numbers, and the rest is determined, so the number of type (c) pairs of pairs is $$\binom{n+1}{2}.$$ Add up.