Donald Knuth and algebraic operations on sums

Question

I'm reading through Knuth's first book in the TAOCP series and I'm on chapter 1.2.3 (Sums and Products).

As this is my first encounter with summation I did take the time to go through what I could find on Khan Academy.

I've gone through the chapter and worked a few examples but I'm specifically having a difficult time understanding all of the four algebraic laws of sums that Knuth lists in the chapter. These are the ones I understand:

• 1. the distributive law and
• 3. interchanging order of summation;

but I do not fully understand

• 2. change of variable and
• 4. manipulating the domain (this one in particular confuses me)

I've had a hard time finding any information by the same names on the internet so I was hoping someone could point me at material to read.

An example of change of variable that I don't necessarily understand:

$$\sum\limits_{R(i)}a_i = \sum\limits_{R(j)}a_j = \sum\limits_{R(p(j))}a_{p(j)}$$

This equation represents two kinds of transformations. In the first case we are simply changing the name of the index variable from i to j. The second case is more interesting: Here p(j) is a function of j that represents a permutation of the relevant values...

I understand what the quote is saying (specifically about permutations) but I do not understand how he proceeds from the far left sum to the far right sum and why that is happening.

An example of manipulating the domain that I don't understand:

$$\sum\limits_{1\le j\le m}a_j + \sum\limits_{m\le j\le n}a_j = \left(\sum\limits_{1\le j\le n}a_j\right) +a_m$$

I understand the left hand side of the equation; but I don't understand the right-hand side - where is the m in $a_m$ coming from now that the sum has been simplified?

Answer 1

Change of variable. This says that it doesn't matter how you order the terms you're summing, as long as you have all of them. As an example, it's obvious that $$ a_1+a_2+\cdots+a_{n-1}+a_n = a_n+a_{n-1}+\cdots+a_2+a_1 $$ so we have $$ \sum_{k=1}^n a_k = \sum_{j=1}^n a_{n+1-j} $$ since the left hand expression is the same as the left sum above and the right expression is the same as the right sum above. In fancy terms, we've just permuted the left-hand indices $\langle 1, 2, \dots n-1, n\rangle\mapsto\langle n, n-1, \dots 2, 1\rangle$.

Another example you might try is to see what the permutation would be that accomplished this: $$ a_1+a_2+\cdots+a_{99}+a_{100} = (a_1+a_3+\cdots+a_{99})+(a_2+a_4+\cdots+a_{100}) $$ such a rewriting might be helpful if the odd-index terms were defined differently than the even-index terms.

Manipulating the domain. What's happening here is that you're collecting the sums together into one and adjusting for the fact that the terms in the two sums overlap. For example $$ \begin{align} \sum_{j=1}^3 a_j + \sum_{j=3}^5 a_j &= (a_1+a_2+a_3)+(a_3+a_4+a_5)\\ &=(a_1+a_2+a_3+a_4+a_5)+a_3\\ &=\left(\sum_{j=1}^5 a_j\right)+a_3 \end{align} $$ since the two sets of summands overlapped at $j=3$, giving us an extra copy of $a_3$. Of course we could do a similar rewrite if the sums overlapped on more than one term.