# Thread: Prove using induction (2)

1. ## Prove using induction (2)

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

$\displaystyle 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

$\displaystyle \mu$ is the Mobius function.

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

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

Consider only the square-free divisors of n, because $\displaystyle \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 $\displaystyle Z_{np} = Z_n = 0$.

If $\displaystyle 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, $\displaystyle 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 $\displaystyle \mu(pd) = \mu(p)\mu(d)=-\mu(d)$. (The Mobius function is multiplicative: $\displaystyle \mu(mn)=\mu(m)\mu(n)$ if (m, n) = 1.)

So the sum, above, is adding up a whole bunch of zeros, so $\displaystyle Z_{np}=0$. This completes the proof.