0
$\begingroup$

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.

  • 1
    $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.2012-06-23
  • 0
    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?2012-06-23
  • 0
    @GenericHuman Thanks.2012-06-23

2 Answers 2

1

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}\;.$$

  • 0
    Hmm thanks. That helped a lot.2012-06-23
0

$$\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}$$