I am reading the very first Donald Knuth book on Algorithms, chapter 1.2.3. "Sum and Products" (p.30).
Donald Knuth introduces operations on sum. But I can't fully understand the 1 example that utilizes two operations:
- 2. change of variable (particularly confused by)
- 4. manipulating the domain
An example of change of variable that fully understand the explanation:
$$\sum\limits_{R(i)}a_i = \sum\limits_{R(j)}a_j = \sum\limits_{R(p(j))}a_{p(j)}$$
However, I can't understand the very first example given in the book: how did we come up with $$2j$$ and how this stores all the variables by changing the variable? The steps are as follows:
$$\sum\limits_{0\le j\le n}a_j=\sum\limits_{0\le j\le n\,j\,even}a_j + \sum\limits_{0\le j\le n \,j\,odd}a_j$$ and then $$\sum\limits_{0\le 2j\le n j\,even}a_{2j} + \sum\limits_{0<=2j+1<=n\,j\,odd}a_{2j+1}$$ $$=\sum\limits_{0<=j<=n/2\,j\,even}a_{2j} + \sum\limits_{0<=j<=n/2j+1\,j\,odd}a_{2j+1}$$
Maybe you have an older edition of the book? In the second edition, Example 1 on page 30 reads $$\begin{align} \sum_{0 \le j \le n} a_j &= \sum_{\substack{0 \le j \le n \\ j \, \text{even}}} a_j + \sum_{\substack{0 \le j \le n \\ j \, \text{odd}}} a_j \\ &= \sum_{\substack{0 \le 2j \le n \\ 2j \, \text{even}}} a_{2j} + \sum_{\substack{0 \le 2j+1 \le n \\ 2j+1 \, \text{odd}}} a_{2j+1} \\ &= \sum_{0 \le j \le n/2} a_{2j} + \sum_{0 \le j < n/2} a_{2j+1} \end{align}$$