Summation of Summation over Divisors of Function of Two Variables

Theorem

Let $c, d, n \in \Z$.

Then:

$\ds \sum_{d \mathop \divides n} \sum_{c \mathop \divides d} \map f {c, d} = \sum_{c \mathop \divides n} \sum_{d \mathop \divides \paren {n / c} } \map f {c, c d}$

where $c \divides d$ denotes that $c$ is a divisor of $d$.

Proof

From Exchange of Order of Summation with Dependency on Both Indices:

$\ds \sum_{\map R i} \sum_{\map S {i, j} } a_{i j} = \sum_{\map {S'} j} \sum_{\map {R'} {i, j} } a_{i j}$

where:

$\map {S'} j$ denotes the propositional function:

there exists an $i$ such that both $\map R i$ and $\map S {i, j}$ hold

$\map {R'} {i, j}$ denotes the propositional function:

both $\map R i$ and $\map S {i, j}$ hold.

We have that:

$\map R d$ is the propositional function:

$d \divides n$

$\map S {d, c}$ is the propositional function:

$c \divides d$

Thus $\map {R'} {d, c}$ is the propositional function:

Both $d \divides n$ and $c \divides d$

This is the same as:

$c \divides n$ and $\dfrac d c \divides \dfrac n c$

Similarly, $\map {S'} c$ is the propositional function:

$\exists d$ such that both $d \divides n$ and $c \divides d$

This is the same as:

$c \divides n$

This gives:

$\ds \sum_{d \mathop \divides n} \sum_{c \mathop \divides d} \map f {c, d} = \sum_{c \mathop \divides n} \sum_{\paren {d / c} \mathrel \divides \paren {n / c} } \map f {c, d}$

Replacing $d / c$ with $d$:

$\ds \sum_{d \mathop \divides n} \sum_{c \mathop \divides d} \map f {c, d} = \sum_{c \mathop \divides n} \sum_{d \mathop \divides \paren {n / c} } \map f {c, c d}$

$\blacksquare$

Sources

• 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $32$