# Concrete Mathematics Iversonian Set Relation Clarification

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,

• Yeah sorry, fixed it already. I just know that most people simply reference it as (Knuth). – Alejandro Jun 10 '13 at 0:41

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

• Wow! Thanks for such an excellent answer! I really understand it now :) So basically, K' is, in essence, all the values of k(j)? – Alejandro Jun 10 '13 at 2:50
• @user1274223: If any value $k$ occurs on the left-hand side (for some $j$), then it must also occur on the right-hand side (where it does not depend on $j$), and therefore yes, it must be in the set $K'$. (But as a technicality, note that in principle you can, if you wish, make $K'$ even larger (put values of $k$ in it that don't occur in any $K(j)$ on the left-hand side) as long as for those "extra" $k$, the corresponding sets $J'(k)$ are empty sets, so that those "extra" $k$" don't actually contribute any values to the right-hand side of the sum.) – ShreevatsaR Jun 10 '13 at 3:05
• I completely get it now! Thanks so much! – Alejandro Jun 10 '13 at 9:52

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

• Thank you for your answer! But could you please explain what you mean by writing the sum symmetrically and slicing horizontally vs vertically? – Alejandro Jun 10 '13 at 2:29
• +1 (Ignore my earlier comment; hadn't read this answer carefully the first time.) – ShreevatsaR Jun 10 '13 at 2:34