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.

$\endgroup$
  • 1
    $\begingroup$ $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. $\endgroup$ – Generic Human Jun 23 '12 at 17:16
  • $\begingroup$ 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? $\endgroup$ – sukunrt Jun 23 '12 at 17:21
  • $\begingroup$ @GenericHuman Thanks. $\endgroup$ – sukunrt Jun 23 '12 at 17:28
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hmm thanks. That helped a lot. $\endgroup$ – sukunrt Jun 23 '12 at 17:29
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.