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?

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

Basically, what is meant there is:

$$\{(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\}$$

| cite | improve this answer | |
  • $\begingroup$ Oh, I've absolutely got it! Thank you. $\endgroup$ – SAT Jun 19 at 7:40
  • $\begingroup$ You are welcome. :-) If you are ok with the answer it would be good to tag it as accepted. $\endgroup$ – trancelocation Jun 19 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.