TAOCP 1.2.3 Exercise 25

Exercise 25. ▶ [15] Consider the following derivation; is anything amiss?

$$\left( \sum_{i=1}^n a_i \right) \left( \sum_{j=1}^n \frac{1}{a_j} \right) = \sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j} = \sum_{1 \le i \le n} \sum_{1 \le i \le n} \frac{a_i}{a_i} = \sum_{i=1}^n 1 = n.$$

Verified: yes
Solve time: 59s

Solution

We are asked to examine the derivation

$\left( \sum_{i=1}^n a_i \right) \left( \sum_{j=1}^n \frac{1}{a_j} \right) = \sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j} = \sum_{1 \le i \le n} \sum_{1 \le i \le n} \frac{a_i}{a_i} = \sum_{i=1}^n 1 = n.$

We check each step carefully using the rules of Section 1.2.3.

The first equality,

$\left( \sum_{i=1}^n a_i \right) \left( \sum_{j=1}^n \frac{1}{a_j} \right) = \sum_{i=1}^n \sum_{j=1}^n \frac{a_i}{a_j},$

is valid by the distributive law for sums, Eq. (4). Here the outer sum is over $i$ and the inner sum is over $j$, and each term $a_i \cdot \frac{1}{a_j} = \frac{a_i}{a_j}$ appears exactly once.

The second equality in the derivation is

$\sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j} = \sum_{1 \le i \le n} \sum_{1 \le i \le n} \frac{a_i}{a_i}.$

This step is incorrect. The inner summation index $j$ was replaced by $i$, and the term $\frac{a_i}{a_j}$ was replaced by $\frac{a_i}{a_i} = 1$. This is a misuse of notation: $i$ and $j$ are distinct indices, and the replacement $j \mapsto i$ is not justified by any of the rules (b), (c), or (d) for manipulating sums. In particular, changing the index variable cannot be done independently in the middle of a double sum without preserving the permutation of values, as in Eq. (5). Here the effect of the incorrect substitution is to remove all terms where $i \ne j$, leaving only the diagonal terms $i = j$. The sum

$\sum_{1 \le i \le n} \sum_{1 \le j \le n} \frac{a_i}{a_j}$

actually contains $n^2$ terms, whereas the modified sum

$\sum_{1 \le i \le n} \sum_{1 \le i \le n} \frac{a_i}{a_i} = \sum_{i=1}^n n \cdot 1 = n^2$

would contain $n^2$ terms, each equal to $1$. Even if one interprets the sum naively as written, it does not reduce to $n$.

The final steps

$\sum_{i=1}^n 1 = n$

are correct only if one has exactly one $1$ for each $i$, but in the previous incorrect step the inner summation was miswritten. Therefore, the final conclusion $n$ is wrong.

The correct evaluation of the original double sum is

$\sum_{i=1}^n \sum_{j=1}^n \frac{a_i}{a_j} = \sum_{i=1}^n \sum_{j=1}^n \frac{a_i}{a_j}.$

No further simplification to a single sum of $n$ terms is valid without additional assumptions on the $a_i$. In general, this double sum contains $n^2$ terms and cannot be collapsed to $n$.

This completes the proof.

∎

Notes

The error illustrates a common pitfall when manipulating double sums: the indices of summation must remain distinct unless a valid permutation or change-of-variable is applied. Rule (b) allows renaming an index, but the replacement $j \mapsto i$ is not a bijection of the relevant set ${1,2,\dots,n}$ and changes the value of the sum.