5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ I think it would be helpful if you explicitly wrote out a short formulation for each of the rules that confuse you. $\endgroup$ – tomasz Jul 23 '13 at 12:35
  • $\begingroup$ @tomasz I've updated my question with examples directly from the book. $\endgroup$ – Ixmatus Jul 23 '13 at 14:09
  • $\begingroup$ In your example the $a_m$ appears in both sums on the left side, i.e. it appears twice. On the right hand side it appears once in in the sum, and therefore the final term $a_m$ must be added to maintain equality. Basically the manipulating the domain is just a statement about the different sets of the indices. $\endgroup$ – gammatester Jul 23 '13 at 14:22
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ A clear explanation, thank you :) $\endgroup$ – Ixmatus Jul 23 '13 at 21:29
  • 1
    $\begingroup$ @Ixmatus. You're welcome. Keep asking. $\endgroup$ – Rick Decker Jul 23 '13 at 23:19
  • $\begingroup$ I suppose I should have looked up the mathematical definition(s) of permutation; I'm reading the wikipedia article on it and it makes much more sense what is meant by p(j) representing a permutation of all relevant values for j in this context. I wonder why he didn't just call it by commutativity? $\endgroup$ – Ixmatus Jul 24 '13 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.