Mobius inversion proof ... not quite a Dirichlet convolution

**hatsoff** · October 16th 2009, 07:17 AM

Prove that for every positive integer $n$ , $\sum_{d|n}\mu(d)d(d)=(-1)^{\omega(n)}$ .

The notation here is $\mu$ denoting Mobius inversion, with

$\omega(n)=\sum_{p|n}1$ (the number of distinct primes dividing $n$ ), and

$d(n)=\sum_{d|n}1=\prod_{p^{\alpha}\parallel n}(\alpha+1)$ (the number of positive divisors of $n$ )

I'm pretty stuck on this one. Any help would be much appreciated!

**NonCommAlg** · October 16th 2009, 09:22 AM

Originally Posted by hatsoff

Prove that for every positive integer $n$ , $\sum_{d|n}\mu(d)d(d)=(-1)^{\omega(n)}$ .

The notation here is $\mu$ denoting Mobius inversion, with

$\omega(n)=\sum_{p|n}1$ (the number of distinct primes dividing $n$ ), and

$d(n)=\sum_{d|n}1=\prod_{p^{\alpha}\parallel n}(\alpha+1)$ (the number of positive divisors of $n$ )

I'm pretty stuck on this one. Any help would be much appreciated!

we know that $\mu(m)=0$ for any integer $m > 1$ which is not square-free. so in your sum you only need to look at those divisors of $n$ which are square-free, i.e. those which are a product of

distinct primes. now there exist exactly $\binom{\omega(n)}{i}$ divisors of $n$ which are product of $i$ distinct primes. also if an integer $m > 1$ is a product of $i$ distinct primes, then $\mu(m)=(-1)^i, \ d(m)=2^i.$

thus: $\sum_{m \mid n} \mu(m) d(m)=\sum_{i=0}^{\omega(n)} (-1)^i \binom{\omega(n)}{i}2^i=\sum_{i=0}^{\omega(n)} \binom{\omega(n)}{i}(-2)^i=(1 \ - \ 2)^{\omega(n)}=(-1)^{\omega(n)}.$

**PaulRS** · October 16th 2009, 04:31 PM

Another approach: $f(n)$ multiplicative $(*)$ implies $F(n)=\sum_{d|n}f(d)$ multiplicative.

So $F(n)=\sum_{y|n}\mu(y)\cdot d(y)$ is multiplicative.

Thus: $F(n)=\prod_{p|n}\left(\sum_{y|p^{s_p}}\mu(y)\cdot d(y)\right)$ where the product goes over the primes dividing $n$ ( $s_p$ is the greatest integer $k$ such that $p^k|n$ )

$\sum_{y|p^{s_p}}\mu(y)\cdot d(y)=\mu(1)\cdot d(1)+\mu(p)\cdot d(p) = -1$ -since $\mu(n)=0$ if n is not square free- hence: $F(n)=\prod_{p|n}\left(-1\right)=(-1)^{\omega(n)}$

(*) $f(n)$ is multiplicative if and only if $f(a\cdot b) = f(a)\cdot f(b)$ whenever $(a,b)=1$

**chiph588@** · October 17th 2009, 03:58 PM

Originally Posted by NonCommAlg

we know that $\mu(m)=0$ for any integer $m > 1$ which is not square-free. so in your sum you only need to look at those divisors of $n$ which are square-free, i.e. those which are a product of

distinct primes. now there exist exactly $\binom{\omega(n)}{i}$ divisors of $n$ which are product of $i$ distinct primes. also if an integer $m > 1$ is a product of $i$ distinct primes, then $\mu(m)=(-1)^i, \ d(m)=2^i.$

thus: $\sum_{m \mid n} \mu(m) d(m)=\sum_{i=0}^{\omega(n)} (-1)^i \binom{\omega(n)}{i}2^i=\sum_{i=0}^{\omega(n)} \binom{\omega(n)}{i}(-2)^i=(1 \ - \ 2)^{\omega(n)}=(-1)^{\omega(n)}.$

Why is $ \binom{\omega(n)}{i} $ in the sum?

**NonCommAlg** · October 17th 2009, 09:17 PM

Originally Posted by chiph588@

Why is $ \binom{\omega(n)}{i} $ in the sum?

i think i explained that in my solution.

Thread: Mobius inversion proof ... not quite a Dirichlet convolution

LinkBack

Thread Tools

Display

Mobius inversion proof ... not quite a Dirichlet convolution

Similar Math Help Forum Discussions

Mobius Inversion problem

Mobius Inversion Formula

Mobius Inversion Formula

Deduce from Mobius inversion formula

Mobius Inversion

Search Tags