M?bius inversion removes a divisor sum. It is the incidence-algebra inverse of summation over the divisibility poset and appears whenever a count mixes primitive objects with their repetitions.
The M?bius function
Definition. \[ \mu(n)= \begin{cases} 1,&n=1,\\ (-1)^r,&n\text{ is a product of }r\text{ distinct primes},\\ 0,&p^2\mid n\text{ for some prime }p. \end{cases} \]
Lemma. \[ \sum_{d\mid n}\mu(d)= \begin{cases}1,&n=1,\\0,&n>1.\end{cases} \] Thus \(\mu*1=\varepsilon\).
Proof. If \(n\) has distinct prime divisors \(p_1,\ldots,p_r\), only squarefree divisors contribute, and \[ \sum_{d\mid n}\mu(d)= \sum_{S\subset\{1,\ldots,r\}}(-1)^{|S|} =(1-1)^r. \]
Inversion theorem
Theorem (M?bius inversion). The relations \[ F(n)=\sum_{d\mid n}f(d) \quad\text{and}\quad f(n)=\sum_{d\mid n}\mu(d)F(n/d) \] are equivalent.
Proof. The first relation is \(F=1*f\). Convolve with \(\mu\): \[ \mu*F=(\mu*1)*f=\varepsilon*f=f. \] The reverse implication follows by convolution with \(1\).
Example (primitive words). Let \(q^n\) count all words of length \(n\) on \(q\) symbols, and let \(P(n)\) count words with least period \(n\). Every word has a unique least period dividing \(n\), so \[ q^n=\sum_{d\mid n}P(d). \] Hence \[ P(n)=\sum_{d\mid n}\mu(d)q^{n/d}. \] Dividing by \(n\) counts primitive necklaces.
Floor-sum form
Theorem. If \[ G(x)=\sum_{n\le x}f(x/n) \] in a setting where the sums are finite, then \[ f(x)=\sum_{n\le x}\mu(n)G(x/n) \] with appropriate floor interpretation.
A basic consequence is the count of coprime integers: \[ \#\{1\le k\le x:\gcd(k,n)=1\} =\sum_{d\mid n}\mu(d)\left\lfloor\frac xd\right\rfloor. \] At \(x=n\), this becomes \[ \varphi(n)=n\sum_{d\mid n}\frac{\mu(d)}d =n\prod_{p\mid n}\left(1-\frac1p\right). \]
Squarefree counting
Example. Since \[ \mu^2(n)=\sum_{d^2\mid n}\mu(d), \] one obtains \[ \sum_{n\le x}\mu^2(n) =\sum_{d\le\sqrt x}\mu(d)\left\lfloor\frac{x}{d^2}\right\rfloor =\frac{x}{\zeta(2)}+O(\sqrt x) =\frac6{\pi^2}x+O(\sqrt x). \] Thus the natural density of squarefree integers is \(6/\pi^2\).