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.

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