# 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$. Jun 19, 2020 at 7:15
• Is it a matter of notation, since I hardly can see how we arrive from this inequality to these result? Jun 19, 2020 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. Jun 19, 2020 at 7:28
• So how should I read that? $$[1 \le j, k \le n]$$ Jun 19, 2020 at 7:30
• I have added an answer where i write the corresponding set notation. Jun 19, 2020 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\}$$