TAOCP 1.2.3 Exercise 8

Exercise 8. [HM25] Find an example of infinite series in which Eq. (7) is false.

Verified: yes
Solve time: 35s

Solution

Equation (7) asserts that

$$ \sum_{R(i)} \sum_{S(j)} a_{ij} = \sum_{S(j)} \sum_{R(i)} a_{ij}. $$

The text states that this operation is not always valid for infinite series. We construct a counterexample.

Define

$$ a_{ij} = \begin{cases} 1, & \text{if } j=i,\ -1, & \text{if } j=i+1,\ 0, & \text{otherwise.} \end{cases} $$

Let

$$ R(i): i \ge 1, \qquad S(j): j \ge 1. $$

First compute the left-hand side of (7). For fixed $i$,

$$ \sum_{j \ge 1} a_{ij} = a_{ii}+a_{i,i+1} = 1+(-1) = 0. $$

Therefore

$$ \sum_{i \ge 1} \sum_{j \ge 1} a_{ij} = \sum_{i \ge 1} 0 = 0. $$

Now compute the right-hand side. For fixed $j=1$,

$$ \sum_{i \ge 1} a_{i1} = 1, $$

since only the term $a_{11}$ is nonzero.

For fixed $j \ge 2$,

$$ \sum_{i \ge 1} a_{ij} = a_{jj}+a_{j-1,j} = 1+(-1) = 0. $$

Hence

$$ \sum_{j \ge 1} \sum_{i \ge 1} a_{ij} = 1+\sum_{j \ge 2} 0 = 1. $$

Thus

$$ \sum_{i \ge 1} \sum_{j \ge 1} a_{ij} = 0, \qquad \sum_{j \ge 1} \sum_{i \ge 1} a_{ij} = 1, $$

so Eq. (7) is false for this infinite series.

The series is not absolutely convergent, since

$$ \sum_{i \ge 1} \sum_{j \ge 1} |a_{ij}| = \sum_{i \ge 1} (|1|+|-1|) = \sum_{i \ge 1} 2, $$

which diverges.

Therefore the hypothesis mentioned in the text after Eq. (10) is essential.

$$ \boxed{ \sum_{i \ge 1} \sum_{j \ge 1} a_{ij} \ne \sum_{j \ge 1} \sum_{i \ge 1} a_{ij} } $$

∎