Möbius function
Other proofs

Another way of proving this formula is by using the identity

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

However it is also possible to prove this identity from first principles. First note that it is trivially true when n = 1. Suppose then that n > 1. Then there is a bijection between the factors d of n for which μ (d) ≠ 0 and the subsets of the set of all prime factors of n. 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 | S | of a non-empty finite set S. First, if | S | = 1, there is exactly one odd-cardinality subset of S, namely S itself, and exactly one even-cardinality subset, namely ∅. Next, if | S | > 1, then divide the subsets of S into two subclasses depending on whether they contain or not some fixed element x in S. There is an obvious bijection between these two subclasses, pairing those subsets that have the same complement relative to the subset { x }. Also, one of these two subclasses consists of all the subsets of the set S \ { x }, 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 { x } -containing subsets of S. 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.
detectable_content:number_placeholders[7], keywords:forbidden_words