# Factoring inequalities using Iverson identity - confused by double summations in Concrete Mathematics book

In chapter 2 section 4 (multiple sums) of Concrete Mathematics(Graham,Knuth,Patashnik) the authors use Iverson Identity to rearrange the variables' bounds. In particular, they start off with a question like this:

$$\begin{equation} S = \displaystyle\sum\limits_{1 \le j < k \le n}^{}{(a_k - a_j)(b_k - b_j)} \end{equation}$$

Continuing by changing the variable to get the lower triangle (from the diagonal): $$\begin{equation} S = \displaystyle\sum\limits_{1 \le k < j \le n}^{}{(a_j - a_k)(b_j - b_k)} \end{equation}$$

Then they go on to add S to itself using the Iverson identity: $$[1 \le j < k \le n] + [1 \le k < j \le n] = [1 \le j, k \le n] - [1 \le j = k \le n]$$

Here is where I feel absolutely lost. I can't understand how they arrive from the two inequalities in the left to the first in the right? On the left, both $$k$$ and $$j$$ have lower bound of 1, yet in the first on the right the $$k$$ is not bounded and $$j$$ appear not to have an upper bound. What am I missing?

• If $1\leq j,k \leq n$, then either $j\lt k$ or $k\lt j$ or $j=k$. So, to have all index pairs on the LHS, you need to remove those index pairs on the RHS where $j=k$. – trancelocation Jun 19 at 7:15
• Is it a matter of notation, since I hardly can see how we arrive from this inequality to these result? – SAT Jun 19 at 7:22
• Indeed, it is a weird notation which might cause confusion. At the end the author wants to express an equality of sets of pairs of indices but uses an unfortunate way to write it down. – trancelocation Jun 19 at 7:28
• So how should I read that? $$[1 \le j, k \le n]$$ – SAT Jun 19 at 7:30
• I have added an answer where i write the corresponding set notation. – trancelocation Jun 19 at 7:33

$$\{(j,k): 1\leq j < k \leq n \text{ or } 1\leq k < j \leq n\}$$ $$= \{(j,k): 1\leq j, k \leq n \} \setminus \{(j,k): 1\leq j= k \leq n\}$$