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

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

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

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

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

$\displaystyle d(n)=\sum_{d|n}1=\prod_{p^{\alpha}\parallel n}(\alpha+1)$ (the number of positive divisors of $\displaystyle 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 $\displaystyle n$, $\displaystyle \sum_{d|n}\mu(d)d(d)=(-1)^{\omega(n)}$.
The notation here is $\displaystyle \mu$ denoting Mobius inversion, with

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

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

I'm pretty stuck on this one. Any help would be much appreciated!
we know that $\displaystyle \mu(m)=0$ for any integer $\displaystyle m > 1$ which is not square-free. so in your sum you only need to look at those divisors of $\displaystyle n$ which are square-free, i.e. those which are a product of

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

thus: $\displaystyle \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: $\displaystyle f(n)$ multiplicative $\displaystyle (*)$ implies $\displaystyle F(n)=\sum_{d|n}f(d)$ multiplicative.

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

Thus: $\displaystyle 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 $\displaystyle n$ ( $\displaystyle s_p$ is the greatest integer $\displaystyle k$ such that $\displaystyle p^k|n$ )

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

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

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

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

thus: $\displaystyle \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 $\displaystyle \binom{\omega(n)}{i}$ in the sum?

5. Originally Posted by chiph588@
Why is $\displaystyle \binom{\omega(n)}{i}$ in the sum?
i think i explained that in my solution.