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

1. ## Mobius inversion proof ... not quite a Dirichlet convolution

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!

2. 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)}.$

3. 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$

4. 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?

5. Originally Posted by chiph588@
Why is $

\binom{\omega(n)}{i}
$
in the sum?
i think i explained that in my solution.