Results 1 to 2 of 2

Math Help - Prove using induction (2)

  1. #1
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Prove using induction (2)

    Define a function \mu on the set of non-negative integers as follows. Let \mu(1)=1, and let \mu(n)=0 if n > 1 and n is divisible by the square of an integer a > 1. Otherwise, if n=p_1p_2...p_k, where the p_i are all distinct primes, then let \mu(n)=(-1)^k. Use induction to prove that for all positive integers n > 1,

    Z_n=\sum_{d>0, d|n}\mu(d)=0
    Last edited by alexmahone; August 13th 2011 at 05:33 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor alexmahone's Avatar
    Joined
    Oct 2008
    Posts
    1,074
    Thanks
    7

    Re: Prove using induction (2)

    References: M�bius function - Mobius function, denoted μ(n); number of odd prime factors of square-free n
    Möbius Function -- from Wolfram MathWorld

    \mu is the Mobius function.

    Proof by multiplicative induction: It is true when n is prime, because Z_p=\mu(1)+\mu(p)=1-1=0.

    Suppose Z_n=0. We will show that Z_{np}=0, where p is an arbitrary prime.

    Consider only the square-free divisors of n, because \mu(d)=0 when d has a square factor.

    If p|n, the square-free divisors of np are the same as the square-free divisors of n, so Z_{np} = Z_n = 0.

    If p \nmid n, the set of square-free divisors of np consists of all the square-free divisors of n together with each divisor multiplied by p.

    So, Z_{np} =\sum_{d>0, d|n}\mu(d)+\mu(pd)

    Since (n, p) = 1, it follows from d|n that (d, p) = 1, and therefore \mu(pd) = \mu(p)\mu(d)=-\mu(d). (The Mobius function is multiplicative: \mu(mn)=\mu(m)\mu(n) if (m, n) = 1.)

    So the sum, above, is adding up a whole bunch of zeros, so Z_{np}=0. This completes the proof.
    Last edited by alexmahone; August 13th 2011 at 05:41 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Use Induction to prove
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: January 11th 2012, 02:12 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. Prove each of the following by induction
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 25th 2010, 10:45 AM
  4. Prove induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 23rd 2008, 07:05 AM
  5. Prove by Induction
    Posted in the Algebra Forum
    Replies: 5
    Last Post: May 30th 2008, 11:16 AM

Search Tags


/mathhelpforum @mathhelpforum