1. ## Arithmetic functions

For two arithmetic functions A(n) and B(n) show that

$\displaystyle \sum_{d|n} A(d)B(n/d) = \sum_{d|n} A(n/d)B(d)$

I figure I need to use the inverse mobius transform somehow but I'm unsure as to what A and B should be in regards to the formula below taken from my notes...

If $\displaystyle F(n) = \sum_{d|n}f(d)$ for every integer $\displaystyle n \geq 1$

then

$\displaystyle f(n)=\sum_{d|n}\mu(n/d)F(d)$ for every integer $\displaystyle n \geq 1$

For two arithmetic functions A(n) and B(n) show that

$\displaystyle \sum_{d|n} A(d)B(n/d) = \sum_{d|n} A(n/d)B(d)$

I figure I need to use the inverse mobius transform somehow but I'm unsure as to what A and B should be in regards to the formula below taken from my notes...

If $\displaystyle F(n) = \sum_{d|n}f(d)$ for every integer $\displaystyle n \geq 1$

then

$\displaystyle f(n)=\sum_{d|n}\mu(n/d)F(d)$ for every integer $\displaystyle n \geq 1$
$\displaystyle d\mid n \iff \frac{n}{d}\mid n$.

Therefore $\displaystyle \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right)$.

Let $\displaystyle q=\frac{n}{d} \implies d=\frac{n}{q}$

Thus $\displaystyle \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{q\mid n} A\left(\frac{n}{q}\right)B(q)$.

In summary, the identity you're trying to prove simply reverses the order in which the terms are summed.

3. Originally Posted by chiph588@
$\displaystyle d\mid n \iff \frac{n}{d}\mid n$.

Therefore $\displaystyle \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right)$.

Let $\displaystyle q=\frac{n}{d} \implies d=\frac{n}{q}$

Thus $\displaystyle \sum_{d\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{\frac{n}{d}\mid n} A(d)B\left(\frac{n}{d}\right) = \sum_{q/mid n} A\left(\frac{n}{q}\right)B(q)$.

In summary, the identity you're trying to prove simply reverses the order in which the terms are summed.
Great thanks, that's actually exactly what I had (except I had k = n/d...) but I didn't think it was right so I scrapped it.