Proof of Möbius Inversion

We prove the Möbius inversion formula using the fundamental property of the Möbius function and Dirichlet convolution algebra.

TheoremMöbius Inversion (Restated)

For arithmetic functions $f, g$ :

g(n) = \sum_{d|n} f(d) \iff f(n) = \sum_{d|n} \mu(d) g(n/d)

ProofProof via Dirichlet Convolution

Step 1: Key Lemma

First, we establish that $\mu * 1 = \delta$ , where $1(n) = 1$ for all $n$ and $\delta(n) = [n=1]$ :

(\mu * 1)(n) = \sum_{d|n} \mu(d) = \begin{cases} 1 & \text{if } n = 1 \\ 0 & \text{if } n > 1 \end{cases}

For $n > 1$ with prime factorization $n = p_1^{a_1} \cdots p_r^{a_r}$ , only squarefree divisors contribute:

\sum_{d|n} \mu(d) = \sum_{S \subseteq \{p_1, \ldots, p_r\}} \mu\left(\prod_{p \in S} p\right) = \sum_{k=0}^{r} \binom{r}{k} (-1)^k = (1-1)^r = 0

Step 2: Forward Direction

Assume $g = f * 1$ . Then:

g(n) = \sum_{d|n} f(d) \cdot 1(n/d) = \sum_{d|n} f(d)

Convolving both sides with $\mu$ :

g * \mu = (f * 1) * \mu = f * (1 * \mu) = f * \delta = f

Therefore:

f(n) = (g * \mu)(n) = \sum_{d|n} g(d) \mu(n/d)

Step 3: Reverse Direction

Assume $f = g * \mu$ . Then:

f(n) = \sum_{d|n} g(d) \mu(n/d)

Convolving both sides with $1$ :

f * 1 = (g * \mu) * 1 = g * (\mu * 1) = g * \delta = g

Therefore:

g(n) = (f * 1)(n) = \sum_{d|n} f(d)

■

ExampleAlternative Combinatorial Proof

For the forward direction, substitute the definition of $g$ :

\sum_{d|n} \mu(d) g(n/d) = \sum_{d|n} \mu(d) \sum_{e | (n/d)} f(e) = \sum_{de|n} \mu(d) f(e)

Rearranging the double sum by setting $m = n/(de)$ :

= \sum_{e|n} f(e) \sum_{d|(n/e)} \mu(d) = \sum_{e|n} f(e) \cdot [\text{$n/e = 1$}] = f(n)

The crucial step uses $\sum_{d|k} \mu(d) = [k=1]$ .

Remark

The proof reveals that Möbius inversion is fundamentally about inverses in the ring of arithmetic functions under Dirichlet convolution. The Möbius function $\mu$ serves as the multiplicative inverse of the constant function $1$ .