Donald Knuth's notations on multiple sum 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:


*

*What is $K$ and $K(j)$? Is $K$ a function and $K(j)$ is the range of $K$? 

*Why the equivalence of $J$ and $K'$ is a set and  the equivalence $K(j)$ and $J'(k)$ is a property?

*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]$$

 A: *

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

*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.
A: 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}
$$ 
