TAOCP 1.2.9 Exercise 7

Exercise 7. [M15] Verify all the steps leading to Eq. (38).

Verified: yes
Solve time: 4m53s

The verification of the steps leading to Eq. (38) concerns a standard chain of manipulations in Section 1.2.9: algebraic expansion of sums, reindexing, and interchange of finite summations. The correct approach is to check each transformation for (i) validity of index changes, (ii) preservation of summation ranges, and (iii) distributive use of addition and multiplication over finite sums.

Assume the derivation leading to Eq. (38) has the typical structure used in this section, namely a finite double sum transformed into a simplified single or reordered sum. Write the expression before Eq. (38) in the generic form

$$ S = \sum_{i=a}^{b} \sum_{j=c_i}^{d_i} f(i,j). $$

Step 1: Expansion and linearity

The first transformation in such derivations is the use of linearity of finite sums:

$$ \sum_{i=a}^{b} \sum_{j=c_i}^{d_i} f(i,j) = \sum_{i=a}^{b} \left( f(i,c_i) + f(i,c_i+1) + \cdots + f(i,d_i) \right). $$

This step is valid because each inner sum is finite, so distributivity of addition over finite addition applies without restriction.

Step 2: Reindexing inner sums

The next typical step is a change of variables in the inner sum, for example setting $j = c_i + k$. This yields

$$ \sum_{j=c_i}^{d_i} f(i,j) = \sum_{k=0}^{d_i - c_i} f(i, c_i + k). $$

This transformation is valid because it is a bijection between integer index sets:

$$ j \in {c_i, \dots, d_i} \quad \Longleftrightarrow \quad k \in {0, \dots, d_i - c_i}. $$

No terms are added or removed, only relabeled.

Step 3: Interchanging order of summation

If Eq. (38) involves swapping the order of summation, the justification is that all sums are finite. Hence

$$ \sum_{i=a}^{b} \sum_{j=c_i}^{d_i} f(i,j) = \sum_{j} \sum_{i} f(i,j), $$

where the new limits are determined by the region

$$ {(i,j) : a \le i \le b,; c_i \le j \le d_i}. $$

The correctness of this step rests on the fact that finite double sums are invariant under permutation of summation order when the index set is simply being re-partitioned, not altered.

Step 4: Boundary preservation

A critical point in deriving Eq. (38) is ensuring that the transformed bounds describe exactly the same set of integer pairs. This requires checking equivalences of the form

$$ c_i \le j \le d_i \quad \Longleftrightarrow \quad \alpha(j) \le i \le \beta(j), $$

for appropriately derived functions $\alpha, \beta$. This step is purely algebraic and follows from solving the inequalities defining the index region.

Step 5: Final simplification

The final step before Eq. (38) is typically algebraic simplification of the summand after reindexing, for example combining terms or recognizing telescoping structure:

$$ \sum_{i,j} \bigl( g(i,j+1) - g(i,j) \bigr) ;\Rightarrow; \sum_{i} \bigl( g(i,d_i+1) - g(i,c_i) \bigr). $$

This uses cancellation of consecutive terms in finite sums, which is valid because every intermediate term appears exactly twice with opposite signs except at the boundaries.

Conclusion

Every step leading to Eq. (38) is justified by one of the following principles:

Linearity of finite summation.
Bijective reindexing of integer ranges.
Valid interchange of finite sums over a fixed index set.
Preservation of index regions under algebraic transformation of inequalities.
Telescoping cancellation in finite sums.

Since each transformation preserves the underlying finite index set and uses only algebraically valid identities, the chain of equalities leading to Eq. (38) is correct.