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?