Editing Möbius function (section)

=== Proof of the formula for the sum of <math>\mu</math> over divisors ===
The formula

:<math>\sum_{d \mid n} \mu(d)=
\begin{cases}
1 & \text{if } n=1, \\
0 & \text{if } n>1
\end{cases}</math>

can be written using [[Dirichlet convolution]] as:
<math>1 * \mu = \varepsilon</math>
where <math>\varepsilon</math> is the [[Dirichlet convolution#Properties|identity under the convolution]].

One way of proving this formula is by noting that the Dirichlet convolution of two [[multiplicative functions]] is again multiplicative. Thus it suffices to prove the formula for powers of primes. Indeed, for any prime 
<math>p</math> and for any <math>k>0</math>
:<math>1 * \mu (p^k) = \sum_{d \mid p^k} \mu(d)= \mu(1)+\mu(p)+\sum_{1<m<=k}\mu(p^m)=1-1+\sum0=0=\varepsilon(p^k)</math>,
while for <math>n=1</math>
:<math>1 * \mu (1) = \sum_{d \mid 1} \mu(d)= \mu(1) =1 =\varepsilon(1)</math>.

====Other proofs====
Another way of proving this formula is by using the identity

:<math>\mu(n) = \sum_{\stackrel{1\le k \le n }{\gcd(k,\,n)=1}} e^{2\pi i \frac{k}{n}},</math>

The formula above is then a consequence of the fact that the <math>n</math>th roots of unity sum to 0, since each <math>n</math>th root of unity is a primitive <math>d</math>th root of unity for exactly one divisor <math>d</math> of <math>n</math>.

However it is also possible to prove this identity from first principles. First note that it is trivially true when <math>n=1</math>. Suppose then that <math>n>1</math>. Then there is a bijection between the factors <math>d</math> of <math>n</math> for which <math>\mu(d)\neq 0</math> and the subsets of the set of all prime factors of <math>n</math>. The asserted result follows from the fact that every non-empty finite set has an equal number of odd- and even-cardinality subsets.

This last fact can be shown easily by induction on the cardinality <math>|S|</math> of a non-empty finite set <math>S</math>. First, if <math>|S|=1</math>, there is exactly one odd-cardinality subset of <math>S</math>, namely <math>S</math> itself, and exactly one even-cardinality subset, namely <math>\emptyset</math>. Next, if 
<math>|S|>1</math>, then divide the subsets of <math>S</math> into two subclasses depending on whether they contain or not some fixed element <math>x</math> in <math>S</math>. There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset <math>\{x\}</math>. Also, one of these two subclasses consists of all the subsets of the set <math>S\setminus\{x\}</math>, and therefore, by the induction hypothesis, has an equal number of odd- and even-cardinality subsets. These subsets in turn correspond bijectively to the even- and odd-cardinality <math>\{x\}</math>-containing subsets of <math>S</math>. The inductive step follows directly from these two bijections.

A related result is that the binomial coefficients exhibit alternating entries of odd and even power which sum symmetrically.