Thread: Prove using induction (2)

Define a function on the set of non-negative integers as follows. Let , and let if n > 1 and n is divisible by the square of an integer a > 1. Otherwise, if , where the are all distinct primes, then let . Use induction to prove that for all positive integers n > 1,

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

is the Mobius function.

Proof by multiplicative induction: It is true when n is prime, because .

Suppose . We will show that , where p is an arbitrary prime.

Consider only the square-free divisors of n, because 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 .

If , 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,

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

So the sum, above, is adding up a whole bunch of zeros, so . This completes the proof.