TAOCP 1.2.4 Exercise 32

Exercise 32. [M18] Prove the double-summation identity

$$\sum_{d \mid n}\sum_{c \mid d} f(c,d)=\sum_{c \mid n}\sum_{d \mid (n/c)} f(c,cd),$$

for any function $f(x,y)$.

Verified: yes
Solve time: 2m11s

Solution

Every divisor pair $(c,d)$ that appears on the left-hand side satisfies

$$ c \mid d,\qquad d \mid n. $$

Hence there exists an integer $e$ such that

$$ d=ce. $$

Since $d \mid n$, we have

$$ ce \mid n, $$

therefore

$$ e \mid \frac{n}{c}. $$

Conversely, if

$$ c \mid n,\qquad e \mid \frac{n}{c}, $$

and if we define

$$ d=ce, $$

then

$$ d \mid n, $$

because $ce \mid n$, and also

$$ c \mid d. $$

Thus the correspondence

$$ (c,d)\longleftrightarrow (c,e),\qquad e=\frac{d}{c}, $$

is a bijection between the set

$$ {(c,d): c\mid d,\ d\mid n} $$

and the set

$$ \left{(c,e): c\mid n,\ e\mid \frac{n}{c}\right}. $$

Under this change of variables,

$$ f(c,d)=f(c,ce). $$

Therefore

$$ \sum_{d \mid n}\sum_{c \mid d} f(c,d) = \sum_{c \mid n}\sum_{e \mid (n/c)} f(c,ce). $$

Replacing the dummy variable $e$ by $d$ gives

$$ \sum_{d \mid n}\sum_{c \mid d} f(c,d) = \sum_{c \mid n}\sum_{d \mid (n/c)} f(c,cd). $$

Hence

$$ \boxed{ \sum_{d \mid n}\sum_{c \mid d} f(c,d) = \sum_{c \mid n}\sum_{d \mid (n/c)} f(c,cd) }. $$

This completes the proof.

∎