I do not understand a lot of cases of Knuth's summation notation in Concrete Mathematics. In general, I cannot seem to get a grasp on the commutative law as applied to manipulating sums. The commutative law is stated:
$$\sum_{k \in K}a_{k}=\sum_{p(k) \in K}a_{p(k)}$$
$K$ is a set of integers and $p(k)$ is any permutation of the integers in that set.
My biggest issue arises with cases such as this:
$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0 \leq n-k \leq n}(a+b(n-k))=\sum_{0 \leq k \leq n}(a+bn-bk)$$
How can you justify that the last two expressions are equivalent? I am also struggling with the following example:
$$\sum_{1 \leq j < k \leq n}\frac{1}{k-j}=\sum_{1 \leq j < k+j \leq n}\frac{1}{k}=\sum_{1 \leq k \leq n}\sum_{1 \leq j \leq n-k}\frac{1}{k}$$
To be clear, I understand the substitution. I do not, however, understand the way he expanded the sum and chose those lower bounds and upper bounds. Could anyone possibly explain this notation in the simplest way possible, but no simpler?
Best Answer
I shall promote my comment regarding the first part to a full answer. As I said, consider
$$\sum_{0\leq k\leq n}(a+bk)=(a+0\cdot b)+(a+1\cdot b)+\cdots+(a+(n-1)\cdot b)+(a+n\cdot b)$$
and contrast with
$$\sum_{0\leq k\leq n}(a+(n-k)b)=(a+(n-0)\cdot b)+(a+(n-1)\cdot b)+\cdots+(a+(n-(n-1))\cdot b)+(a+(n-n)\cdot b)$$
Writing the sums in this way shows that one is merely a reversal of the other, and this indeed is an application of addition's commutativity. (The substitutions done by Marvis and Brian say the same thing, only in algebraic language.)
Since you've said that you're working on Concrete Mathematics, I feel even more justified to show the utility of Iverson brackets in manipulating double sums. (Effectively, this is a restatement of Marvis's and Brian's answers in Iversonian form.)
As a reminder of the definition, $[p]$ evaluates to $1$ if condition $p$ is true, and $0$ if condition $p$ is false. Iverson brackets have the useful property that $[p\text{ and }q]=[p][q]$, which will be important here.
We can rewrite your double sum in Iversonian form as
$$\sum_j\sum_k\frac{[1\leq j<k\leq n]}{k-j}$$
(It's a bit of an abuse that only one summation sign was written when two indices are indicated, but let's forgive that.) Note that we can effectively treat the sum as an infinite summation, since the Iverson brackets zero out any terms that do not satisfy the condition it encloses.
As already explained in the previous answers, we can do the substitution $k\mapsto k+j$ like so:
$$\begin{align*}\sum_j\sum_k\frac{[1\leq j<k+j\leq n]}{k+j-j}&=\sum_j\sum_k\frac{[1\leq j<k+j\leq n]}{k}\\&=\sum_j\sum_k\frac{[1\leq k<k+j\leq n]}{k}\end{align*}$$
Note that here it was fine not to touch the summation's indices, since if $-\infty < j < \infty$ and $-\infty < k < \infty$, we also have $-\infty < j+k < \infty$. We are also justified in replacing the $j$ in the second line with a $k$, since $k < k+j$ in the range being considered
We can now split the Iverson factor using the property I mentioned earlier. In particular, we have
$$\begin{align*}\sum_j\sum_k\frac{[1\leq k<k+j\leq n]}{k}&=\sum_k\sum_j\frac{[(1\leq k\leq n)\text{ and }(1\leq j+k\leq n)]}{k}\\&=\sum_k\sum_j\frac{[1\leq k\leq n][1\leq j+k\leq n]}{k}\end{align*}$$
(I've also taken the liberty of swapping summation order in the meantime.)
We can rearrange the last bit to
$$\sum_k\sum_j\frac{[1\leq k\leq n][-k\leq j\leq n-k]}{k}=\sum_k\sum_j\frac{[1\leq k\leq n][1\leq j\leq n-k]}{k}$$
How did this happen? Due to the conditions $1\leq j\leq n$ and $1\leq k\leq n$, we can zero out all the terms from $j=-k$ to $j=0$. A final rearrangement leads to
$$\sum_k [1\leq k\leq n] \sum_j [1\leq j\leq n-k] \frac1{k}=\sum_{1\leq k\leq n} \sum_{1\leq j\leq n-k} \frac1{k}$$
and we are done.