Results 1 to 5 of 5

Math Help - 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 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!
    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 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)}.
    Last edited by NonCommAlg; October 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: 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
    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 \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 <br /> <br />
\binom{\omega(n)}{i}<br />
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 <br /> <br />
\binom{\omega(n)}{i}<br />
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: October 31st 2010, 07:36 PM
  2. Mobius Inversion Formula
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: February 26th 2010, 08:46 AM
  3. Mobius Inversion Formula
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: December 10th 2009, 12:35 PM
  4. Deduce from Mobius inversion formula
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: April 15th 2008, 03:40 PM
  5. Mobius Inversion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 26th 2008, 04:42 PM

Search Tags


/mathhelpforum @mathhelpforum