Editing Möbius function (section)

====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.