# Intuition for the following change of index of sumation

I am working through Concrete Mathematics. I came across the following change in index of summation while going through the number theory chapter.

$$\sum_{m|n}^{ } \sum_{k|m}{ } a_{k,m} = \sum_{k|n}^{ } \sum_{l|(n/k)} a_{k,kl}$$

If I list out the complete summation mechanically I can verify that both the sides are the same. The Left hand side is (I think) for every divisor $m$ of $n$, you have $k$ running through the divisors of $n$ less or equal to $m$. But I can't find some interpretation of the RHS. So I want to know how the right hand side is rearranging the terms.

• $l\mid n/k$ can be rewritten as $m=kl\mid n$, which is equivalent to $k\mid m\mid n$. So the first $\sum$ of the RHS is over the set of $k$ such that there exists $m$ such that $k\mid m\mid n$ (which is equivalent to $k\mid n$), and the second $\sum$ is over the set of such $m$ when $k$ and $n$ are fixed. – Generic Human Jun 23 '12 at 17:16
• Ok so what it's doing is it takes k first and then the second summation goes to all m such that k|m|n. This is done by taking m = kl and modifying it for l? – sukunrt Jun 23 '12 at 17:21
• @GenericHuman Thanks. – sukunrt Jun 23 '12 at 17:28

On both sides you’re taking a sum of $a_{k,m}$ over all pairs $\langle k,m\rangle$ such that $k\mid m$ and $m\mid n$. The first summation chooses the middle element first and then sums over its divisors; the second chooses the smallest element first and then sums over the possible intermediate elements. For a fixed $k$ dividing $n$, as $l$ runs over divisors of $\frac{n}k$ in the inner summation on the righthand side, $kl$ runs over all $m$ such that $k\mid m$ and $m\mid n$. Both are thus equal to
$$\sum_{k\mid m\text{ and }m\mid n}a_{k,m}\;.$$
$$\begin{eqnarray}\rm \{\!\ (k,m) &:&\rm\ \phantom{ k\,|\, n,\ \!\ } m\,|\, n,\ \ k\ \ |\ \ m\!\ \} \\ =\ \rm\{\!\ (k,m) &:&\rm\ \phantom{ k\,|\, n,}\ \ kl\,|\, n,\ \ kl\!=\!m\!\ \} \\ =\ \rm\{\!\ (k,kl) &:&\rm\ k\,|\, n,\ \ l\,|\, n/k\!\ \} \end{eqnarray}$$