The Möbius Inversion Formula

Recall from The Möbius Function page that the Möbius Function $\mu$ is an arithmetic function defined by:

(1)

\begin{align} \quad \mu(n) = \left\{\begin{matrix}0 & \mathrm{if} \: n \: \mathrm{is \: NOT \: square free.}\\ (-1)^{\omega (n)} & \mathrm{if} \: n \: \mathrm{is \: square \: free.} \end{matrix}\right. \end{align}

We proved that $\mu$ is a multiplicative function. We are now ready to state a very important result called the Möbius inversion formula.

Theorem 1 (The Möbius Inversion Formula): If $\displaystyle{F(n) = \sum_{d|n} f(d)}$ then $\displaystyle{f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right)}$.

That is, if $F = f * 1$ then $f = \mu * F$.

• Proof: We have that:

(2)

\begin{align} \quad \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) &= \sum_{d|n} \mu(d) \sum_{d|n} f \left ( \frac{n}{d} \right ) \\ &= \sum_{d|n} \mu(d) \sum_{e|\frac{n}{d}} f(e) \\ &= \sum_{d|n} \sum_{e|\frac{n}{d}} \mu(d) f(e) \end{align}

• If $e | \frac{n}{d}$ we have that $d | \frac{n}{e}$. Using this and The Dirichlet Convolution μ * 1 = ꙇ, we have that:

(3)

\begin{align} \quad \sum_{e|n} \mu (d) F \left ( \frac{n}{d} \right ) &= \sum_{e|n} \sum_{d|\frac{n}{e}} \mu(d) f(e) \\ &= \sum_{e|n} \left ( f(e) \cdot \sum_{d|\frac{n}{e}} \mu(d) \right ) \\ &= \sum_{e|n} f(e) \iota \left ( \frac{n}{e} \right ) \\ &= \sum_{e|n} f(e) \cdot \left\{\begin{matrix} 0 & \mathrm{if} \: e \neq n \\ 1 & \mathrm{if} \: e = n \end{matrix}\right. \\ &= f(n) \end{align}

• Hence:

(4)

\begin{align} \quad f(n) = \sum_{d|n} \mu(d) F \left ( \frac{n}{d} \right ) \quad \blacksquare \end{align}

Corollary 1: If $\displaystyle{F(n) = \sum_{d|n} f(d)}$ then $F$ is multiplicative if and only if $f$ is multiplicative.

• Proof: $\Rightarrow$ Suppose that $F$ is multiplicative. By the Möbius inversion formula, since $F = f * 1$ we have that $f = \mu * F$. Since $\mu$ and $F$ are multiplicative, so is $f$.

• $\Leftarrow$ Suppose that $f$ is multiplicative. Since $f$ and $1$ are multiplicative, so is $F = f * 1$. $\blacksquare$