# Thread: Prove using induction (2)

1. ## 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$

2. ## 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.