0
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\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$ Jun 19, 2020 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$
    – Karina
    Jun 19, 2020 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$ Jun 19, 2020 at 7:28
  • $\begingroup$ So how should I read that? $$[1 \le j, k \le n]$$ $\endgroup$
    – Karina
    Jun 19, 2020 at 7:30
  • $\begingroup$ I have added an answer where i write the corresponding set notation. $\endgroup$ Jun 19, 2020 at 7:33

1 Answer 1

0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Oh, I've absolutely got it! Thank you. $\endgroup$
    – Karina
    Jun 19, 2020 at 7:40
  • $\begingroup$ You are welcome. :-) If you are ok with the answer it would be good to tag it as accepted. $\endgroup$ Jun 19, 2020 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.