The Möbius Inversion Formula

# 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:

\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:

\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:

\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$