Donald Knuth's summation notation confuses me.

Question

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?

Answer 1

Ginger Rogers did everything Fred Astaire did, only backwards and in high heels.

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.

Answer 2

Probably a change of variables may be of help to make things clear.

For instance, in the summation $$\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)$$

Consider $\displaystyle \sum_{0 \leq k \leq n}(a+bk)$. Let $k_1 = n-k$. Hence, we get that $$\displaystyle \sum_{0 \leq k \leq n}(a+bk) = \sum_{0 \leq n-k_1 \leq n} (a+b(n-k_1))$$ Now $0 \leq n-k_1 \leq n$ is same as $0 \leq k_1 \leq n$. Hence, we get that $$\displaystyle \sum_{0 \leq k \leq n}(a+bk) = \sum_{0 \leq n-k_1 \leq n} (a+b(n-k_1)) = \sum_{0 \leq k_1 \leq n} (a+bn - bk_1)$$ Note that $k_1$ is just a dummy variable and hence you can as well replace it with $k$. Hence, $$\displaystyle \sum_{0 \leq k \leq n}(a+bk) = \sum_{0 \leq k \leq n} (a+bn - bk)$$

In general, the change of variable is the function $k_1 = p(k)$ in $$\sum_{k \in K}a_{k}=\sum_{k_1 \in K}a_{k_1}$$ Note that $p(k)$ is a permutation i.e. a bijection from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n\}$. So $\sum_{k_1 \in K}a_{k_1}$ is just the same as $\sum_{k \in K}a_{k}$ just that the order in which you add the elements are different and thanks to commutativity, both remain the same. For instance, in the previous example, $k_1 = p(k) = n-k$, which is nothing but adding the elements in the reverse order.

Similarly, in the second summation, $$\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}$$

Let $k_1 = k-j$ i.e. $k = k_1 + j$. Hence, we get that $$\sum_{1 \leq j < k \leq n}\frac{1}{k-j}=\sum_{1 \leq j < k_1+j \leq n}\frac{1}{k_1+j-j}=\sum_{1 \leq j < k_1+j \leq n}\frac{1}{k_1}$$

Now we have $1 \leq j < k_1+j \leq n$. To understand this summation.

First let $k_1=1$. We then get that $1 \leq j < j+1 \leq n$. This gives us $1 \leq j \leq n-1$.

Now let $k_1 = 2$. We then get that $1 \leq j < j+2 \leq n$. This gives us $1 \leq j \leq n-2$.

Now let $k_1 = 3$. We then get that $1 \leq j < j+3 \leq n$. This gives us $1 \leq j \leq n-3$.

Hence, you see that for $1 \leq k_1 \leq n-1$, we find that $1 \leq j \leq n-k_1$. Hence, the summation becomes

$$\sum_{1 \leq j < k \leq n}\frac{1}{k-j}=\sum_{1 \leq j < k_1+j \leq n}\frac{1}{k_1+j-j}=\sum_{1 \leq j < k_1+j \leq n}\frac{1}{k_1} = \sum_{1 \leq k_1 \leq n-1} \sum_{1 \leq j \leq n-k_1}\frac{1}{k_1}$$

The reason we set $k_1$ a fixed value and look at the range of $j$ is because we want to sum over $j$ first as a function of $k_1$ and then sum over $k_1$. The reason we want to sum over $j$ first i.e. $\displaystyle \sum_{1 \leq j \leq n-k_1}\frac{1}{k_1}$, is that this sum is easy to evaluate is easier to evaluate. The inner sum i.e.$\displaystyle \sum_{1 \leq j \leq n-k_1}\frac{1}{k_1}$ is $\dfrac{n-k_1}{k_1}$.

You could also perform the summation in the reverse order. This will give you $$\sum_{j=1}^{n} \sum_{k_1 = 1}^{n-j} \frac1{k_1}$$ However, the inner sum is not easy to simplify as in the earlier case.

To conlude the post, interchanging summation/integrals is a very powerful technique in general and can be of real use to prove non-trivial results.

Answer 3

After a lot of concentration and failure, here's my answer :)

\begin{align} S_n&=\sum_{1 \leq j < k \leq n}\frac{1}{k-j}\\ \text{Let } k&=j+u\\ S_n&=\sum_{1 \leq j < j+u \leq n}\frac{1}{u}\\ j+u \leq n &\rightarrow j \leq n-u\\ 1 \leq j \text{ and } j \leq n-u &\rightarrow 1 \leq j \leq n-u\\ 1 \leq n-u &\rightarrow u \leq n-1\\ j < u+j &\rightarrow 0 < u\\ 0 < u &\rightarrow 1 \leq u\\ \therefore 1 \leq &u \leq n-1\\ \text{Thus } S_n&=\sum_{1 \leq j \leq n-u}\sum_{1 \leq u \leq n-1}\frac{1}{u}\\ &=\sum_{1 \leq u \leq n-1}\frac{n-u}{u}\\ \frac{n-u}{u}&=0 \text{ at } u=n\\ \therefore S_n&=\sum_{1 \leq u \leq n}\frac{n-u}{u}\\ &=n\sum_{1 \leq u \leq n}\frac{1}{u}-\sum_{1 \leq u \leq n}1\\ &=nH_n-n\\ &=n\left(H_n-1 \right) \end{align}

(The other sum seems trivial in comparison.)

P.S. I posted this only as a conclusion to the question and demonstrating that I understand the question now due to the help of Math.SE. I also wanted to share my train of thought with the users here.

Answer 4

Let’s take a look at $$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0 \leq n-k \leq n}\Big(a+b(n-k)\Big)\;.$$ It may help to look at this as a substitution. Let $j=n-k$; then $k=n-j$, so

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0\le n-j\le n}\Big(a+b(n-j)\Big)\;.$$ But $0\le n-j\le n$ iff $-n\le j-n\le 0$ iff $0\le j\le n$ (by multiplying by $-1$ and adding $n$), so

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0\le j\le n}\Big(a+b(n-j)\Big)\;.$$ Now just rename $j$ to $k$, and you have the desired.

$$\sum_{0 \leq k \leq n}(a+bk)=\sum_{0\le k\le n}\Big(a+b(n-k)\Big)\;.$$ When you’re first learning this, it often helps to write out the substitution explicitly, as I’ve done here.

For $$\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}\;,\tag{1}$$ let $i=k-j$. Note that $1\le j<k\le n$ iff $1\le j<j+i\le n$, so

$$\sum_{1\le j<k\le n}\frac1{k-j}=\sum_{1\le j<j+i\le n}\frac1i\;.$$ If you now rename $i$ to $k$, you have $$\sum_{1\le j<k\le n}\frac1{k-j}=\sum_{1\le j<j+k\le n}\frac1k\;,\tag{2}$$ which is clearly the same as the middle summation in $(1)$. Now what are the possible values of $k$? It has to be at least $1$, since $j+k>j$, and it can be at most $n-1$, when $j=1$ and $j+k=n$. Thus, if we break down the second summation in $(2)$ by lumping together all terms with the same $k$, we’ll have something of the form $$\sum_{1\le k\le n-1}\text{something}\;.\tag{3}$$ (Don’t worry about the $n-1$ for now.) For each fixed value of $k$, $j$ runs from a minimum of $1$ up to whatever makes $j+k$ equal to $n$: that’s the biggest allowable value of $j+k$. Clearly that’s $j=n-k$, so for each $k$, $j$ runs from $1$ through $n-k$. We can now replace the $\text{something}$ in $(3)$:

$$\sum_{1\le j<j+k\le n}\frac1k=\sum_{1\le k\le n-1}\left(\sum_{1\le j\le n-k}\frac1k\right)=\sum_{1\le k\le n-1}\sum_{1\le j\le n-k}\frac1k\;.$$

This isn’t quite the same as Knuth’s $$\sum_{1\le k\le n}\sum_{1\le j\le n-k}\frac1k\;,$$ but if you look closely, you’ll see that these expressions actually have the same value: when $k=n$ in Knuth’s the inner sum ranges over $1\le j\le 0$, so it’s an empty sum and equals $0$.