# 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:

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]$$
• You've asked seven questions and have accepted none. It's considered polite, a couple of days after you've asked a question, to look over the answers and select one which you've found most helpful (if any) and accept it, by clicking on the check mark next to the answer. This rewards both you and the answerer with some reputation points and might enhance your chance of getting people to answer your future questions. – Rick Decker Sep 10 '13 at 0:17

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}$$
• In this case, can we say $K(j)=J'(k)$? – MS.Kim Aug 27 '15 at 5:37
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.