Concrete Mathematics Iversonian Set Relation Clarification

Question

Sorry for asking a very dumb question, but in Concrete Mathematics(Graham,Knuth,Patashnik), chapter 2 section 4, Knuth talks about this formula called "Rocky Road".

This is the formula to use when you want to interchange the order of summation of a double sum whose inner sum's range depends on the index variable of the outer sum, like this:

\begin{equation} \displaystyle\sum\limits_{j = 1}^{n}{\displaystyle\sum\limits_{k = j}^{n}{a_j,_k}} \end{equation}

The rocky road formula is as follows: \begin{equation} \displaystyle\sum\limits_{j \in J}^{}{\displaystyle\sum\limits_{k \in K(j)}} = \displaystyle\sum\limits_{k \in K'}{\displaystyle\sum\limits_{j \in J'(k)}} \end{equation}

With the requirement that the sets $J,K(j),K', \text{and} J'(k)$ be related in such a way that: \begin{equation} [j \in J][k \in K(j)] = [k \in K'][j \in J'(k)] \end{equation}

My understanding of this, is that the set $K'$ is basically the "bounds" that $k$ has, sort of like its restrictions. For the first sum I wrote, I would think that K' be the set {j,j+1,...,n} and since j starts at 1, K' is really just the set of the values $1 \rightarrow n$. However, I can't really figure out $J'(k)$ here , or even if my understanding of $K'$ is right. Can anyone give me some pointers or put me in the right track as to understanding this set relation?

Thanks,

Answer 1

The requirement is basically saying that you must sum over the same set of numbers $a_{j,k}$ on both sides: if a particular pair $(j, k)$ occurs somewhere on the left-hand side, then $(k, j)$ must occur somewhere on the right-hand side, and vice-versa.

Looking at some simple examples might help.

---

$$\sum_{j=1}^{n} \sum_{k=1}^{n} a_{j,k} = \sum_{k=1}^{n} \sum_{j=1}^{n} a_{j,k}$$

It should be clear to you that the above equation holds: Here, you're summing over all numbers $a_{j,k}$ such that $1 \le j \le n$ and $1 \le k \le n$. In terms of the notation, $J = \{1, 2, \dots, n\}$, $K(j) = \{1, 2, \dots, n\}$, $K' = \{1, 2, \dots, n\}$, and $J'(k) = \{1, 2, \dots, n\}$ (all the same).

---

$$\sum_{j=1}^{n} \sum_{k=j}^{n} a_{j,k} = \sum_{k=1}^{n} \sum_{j=1}^{k} a_{j,k}$$

Here, if you view the numbers $a_{j,k}$ as being laid out in an $n \times n$ matrix, then on the left hand side, you're summing over the "upper triangle" (numbers on or above the diagonal) of the matrix: for each row ($j$), you add up numbers from only those columns ($k$) that occur at $j$ (on the diagonal) or more (to the right). If you try to describe this "upper triangle" write it by columns instead, then for each column $k$, you must add up the numbers from the rows $j$ that either occur on the diagonal (so, at $k$) or above it (so, smaller $j'$). That gives the right-hand side.

How the notation helps here (or may help) is that you can say $[j \in J] = [1\le j \le n]$, and $[k \in K(j)] = [j\le k \le n]$, so after taking $K' = \{1, 2, \dots, n\}$ so that $[k \in K'] = [1 \le k \le n]$, you're trying to find $J'(k)$ such that $$\begin{align} [k \in K'][j \in J'(k)] &= [j \in J][k \in K(j)] \\ [1 \le k \le n][j \in J'(k)] &= [1 \le j \le n][j \le k \le n] = [1 \le j \le k \le n]\\ \end{align}$$ which says you must take $[j \in J'(k)] = [1 \le j \le k]$ or $J'(k) = \{1, 2, \dots, k\}$. Thus the sum on the right-hand side.

Whether the notation helps you more than thinking directly, varies from person to person and depends on you.

---

A final example, slightly less trivial, which you can work out for yourself:

$$\sum_{j=1}^{n} \sum_{k\text{ divides }j} a_{j, k} = \sum_{k=1}^{n} \sum_{\substack{j\text{ is a multiple of }k\\\text{and }j \le n}} a_{j, k}$$

Answer 2

I like that book a lot, but I think this is being made more complicated than it really is.

I think it easier to write the sum symmetrically as $ \sum\limits_{(j,k) \in S} $ where $ S = \{ (j,k) | j \in J, k \in J(k) \} $. Then you can think of $ S \subset \mathbb{Z}^2 $, and exchanging the order of the sum corresponds to slicing horizontally rather than vertically. That is, $ J'(k) $ is the horizontal slice of $ S $ at y-coordinate $ k $. So as you correctly point out $ K' = \pi_2 S$, the projection to second coordinate. (Actually, all you really need is $ \pi_2 S \subset K' $, since if $ J'(k) $ is empty. you won't sum over that k.)

For your example, $ S = \{ (j,k) | \; 1 \leq j \leq n, \; 1 \leq \ k \leq n, \; j \leq k \} $. From this read immediately that $ J'(k) = \{ j | \; 1 \leq j \leq n, \; j \leq k \} $.