TAOCP 1.2.3 Exercise 18

We are to transform $\sum_{R(i)} \sum_{S(i,j)} a_{ij}$ according to Eq.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.3: Sums and Products

Exercise 18. [M20] Show how to interchange the order of summation as in Eq. (9) given that $R(i)$ is the relation “$n$ is a multiple of $i$” and $S(i, j)$ is the relation “$1 \le j < i$.”

Verified: yes
Solve time: 34s

Solution

We are to transform

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

according to Eq. (9), where

$R(i) : \text{``$n$ is a multiple of $i$''}$

and

$S(i,j) : \text{``$1 \le j < i$''}.$

Thus the given sum is

$\sum_{i \mid n} \sum_{1 \le j < i} a_{ij},$

where $i \mid n$ means that $i$ divides $n$.

By Eq. (9), the transformed summation has the form

$\sum_{S'(j)} \sum_{R'(i,j)} a_{ij},$

where $S'(j)$ is the relation

there exists an integer $i$ such that $i \mid n$ and $1 \le j < i$,

and where $R'(i,j)$ is the relation

$i \mid n$ and $1 \le j < i$.

We first simplify $S'(j)$. The condition $1 \le j < i$ implies $j \ge 1$. Also, since $i \mid n$, every such $i$ satisfies $i \le n$ when $n>0$. Hence

$1 \le j < i \le n,$

so necessarily

$1 \le j < n.$

Conversely, if $1 \le j < n$, then $i=n$ satisfies both $i \mid n$ and $1 \le j < i$. Therefore

$S'(j) : 1 \le j < n.$

Next we simplify $R'(i,j)$. The relation already has the form

$i \mid n \quad \text{and} \quad 1 \le j < i.$

Since $j$ is fixed in the inner sum, this may be written more compactly as

$j < i \mid n.$

Therefore the order of summation may be interchanged as

= \sum_{1 \le j < n} \sum_{\substack{i \mid n \ j < i}} a_{ij}.$$ Hence the required transformation is $$\boxed{ \sum_{i \mid n} \sum_{1 \le j < i} a_{ij} = \sum_{1 \le j < n} \sum_{\substack{j < i \ i \mid n}} a_{ij} }.$$