Results 1 to 5 of 5

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

  1. #1
    Senior Member
    Joined
    Feb 2008
    Posts
    410

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by hatsoff View Post
    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)}.$
    Last edited by NonCommAlg; Oct 16th 2009 at 10:04 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    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$
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by NonCommAlg View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by chiph588@ View Post
    Why is $\displaystyle

    \binom{\omega(n)}{i}
    $ in the sum?
    i think i explained that in my solution.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Mobius Inversion problem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Oct 31st 2010, 07:36 PM
  2. Mobius Inversion Formula
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Feb 26th 2010, 08:46 AM
  3. Mobius Inversion Formula
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: Dec 10th 2009, 12:35 PM
  4. Deduce from Mobius inversion formula
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Apr 15th 2008, 03:40 PM
  5. Mobius Inversion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Mar 26th 2008, 04:42 PM

Search Tags


/mathhelpforum @mathhelpforum