Arithmetic functions

**Deadstar** · March 22nd 2010, 04:48 AM

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

$\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 $F(n) = \sum_{d|n}f(d)$ for every integer $n \geq 1$

then

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

**chiph588@** · March 22nd 2010, 08:48 AM

Originally Posted by Deadstar

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

$\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 $F(n) = \sum_{d|n}f(d)$ for every integer $n \geq 1$

then

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

$d\mid n \iff \frac{n}{d}\mid n$ .

Therefore $\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 $q=\frac{n}{d} \implies d=\frac{n}{q}$

Thus $\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.

**Deadstar** · March 22nd 2010, 01:29 PM

Originally Posted by chiph588@

$d\mid n \iff \frac{n}{d}\mid n$ .

Therefore $\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 $q=\frac{n}{d} \implies d=\frac{n}{q}$

Thus $\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.

Thread: Arithmetic functions

LinkBack

Thread Tools

Display

Arithmetic functions

Similar Math Help Forum Discussions

Proof with arithmetic functions

Multiplicative Arithmetic Functions

Arithmetic Progression or Arithmetic Series Problem

Arithmetic Functions

Arithmetic Functions.

Search Tags