Donald Knuth's notations on multiple sum

Question

I am reading Donald Knuth's Concrete Mathematics (2nd Edition) and I am on chapter 2 (Sums).

I have problems in understanding his some notations on multiple sums. I quote his explanations I can't understand from his book.

$$\sum_{j\in J}\sum_{k\in K(j)}a_{j,k}=\sum_{k\in K'}\sum_{j\in J'(k)}a_{j,k}$$ Here the sets $J, K(j), K'$, and $J'(k)$ must be related in such a way that $$[j\in J][k\in K(j)]=[k\in K'][j\in J'(k)]$$ A factorization like this is always possible in principle, because we can let $J=K'$ be the set of all integers and $K(j)=J'(k)$ be the basic property $P(j,k)$ that governs a double sum.

My questions are:

1. What is $K$ and $K(j)$? Is $K$ a function and $K(j)$ is the range of $K$?
2. Why the equivalence of $J$ and $K'$ is a set and the equivalence $K(j)$ and $J'(k)$ is a property?
3. So, if $J$ and $K'$ are sets and $K$ and $J'$ are functions, what will be $J, K(j), K'$ and $J'(k)$ in this case? $$[1\le j\le n][j\le k\le n]=[1\le k\le n][1\le j\le k]$$

Answer 1

As ABC indicated, what Knuth's doing here is looking at the whole space of the $(j, k)$ indices by rows on one side of the equality and by columns on the other. Consider your example in (3): $$ \sum_{j=1}^n\sum_{k=j}^n a_{jk} $$ For each $j$ in the outer sum we have to iterate $k$ in the inner sum. Doing this gives us the $(j, k)$ pairs $$\begin{array}{ccccc} (1,1) & (1, 2) & (1,3) & & \dots & (1, n) \\ & (2, 2) & (2, 3) & (2, 4) & \dots & (2, n) \\ & & (3, 3) & (3, 4) & \dots & (3, n) \\ & & & & \ddots & \\ & & & & & (n, n) \end{array}$$ In this case we have $J=(1\le j \le n), K(j)=(j\le k\le n)$, as in your part (3). Evaluate your sum by rows and you'll have $$ (a_{11}+\cdots+a_{1n})+(a_{22}+\cdots+a_{2n}) +\cdots +(a_{nn}) $$

---

Now do the same thing for the right side, writing it as $$ \sum_{k\in K'}\sum_{j\in J'(k)}a_{jk} $$ What should $K'$ and $J'(k)$ be? Look at the array above, only this time sum it by columns then by rows within each column. You'll have $$ (a_{11})+(a_{12}+a_{22}) + \cdots +(a_{1n}+\cdots+a_{nn}) $$ You'll have the same sum, evaluated in different order. With a bit of thought, you can see that $k$ takes the values $1, 2, \dots , n$ so $K'=(1\le k\le n)$ and for each $k$ the inner sum will take the $j$ values $1, 2, \dots ,k$ so $J'(k)=(1\le j\le k)$ so the sum we started with can be rewritten as $$ \sum_{k=1}^n\sum_{j=1}^ka_{jk} $$

Answer 2

1. $K(j)$, or $K_j$ if you prefer, are sets of indexes that depend on $j$.

2. and 3. What he is saying is that you can put the outer sums to be over all the naturals (by defining the extra summands added to be zero). Example $\sum_{k=0}^{n}\binom{n}{k}=\sum_{n\in\mathbb{Z}}\binom{n}{k}$, where we conveniently define $\binom{n}{k}=0$ for $k>n$ or $k<0$.

The other thing he is saying about $K(j)=J'(k)$ is the following. Look at the actual terms of the summation are functions of the indexes $(j,k)$. The original domain (the indexes on which the original sums are taken) is some set in $\mathbb{Z}\times\mathbb{Z}$. Then $K(j)$ are the sections of this set when you intersect them with the vertical lines $j=$constant. And $J'(k)$ the sections when you intersect it with horizontal lines $k=$constant.