Möbius Inversion Formula
From ProofWiki
Theorem
Let $f$ and $g$ be arithmetic functions.
Then:
- $(1): \quad \displaystyle f \left({n}\right) = \sum_{d \mathop \backslash n} g \left({d}\right)$
iff:
- $(2): \quad \displaystyle g \left({n}\right) = \sum_{d \mathop \backslash n} f \left({d}\right) \mu \left({\frac n d}\right)$
where:
- $d \mathop \backslash n$ denotes that $d$ is a divisor of $n$
- $\mu$ is the Möbius function.
Proof
Let $u$ be the unit arithmetic function and $\iota$ the identity arithmetic function.
Let $*$ denote Dirichlet convolution.
Then equation $(1)$ states that $f = g * u$ and $(2)$ states that $g = f * \mu$.
The proof rests on the following facts:
- $\mu * u = \iota$
- By Properties of Dirichlet Convolution, Dirichlet convolution is commutative, associative and $h * \iota = h$ for all $h$.
We have:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle f = g * u\) | \(\implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle f * \mu = \left({g * u}\right) * \mu\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle f * \mu = g * \left({u * \mu}\right)\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle f * \mu = g\) | \(\displaystyle \) | \(\displaystyle \) |
Conversely:
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle g = f * \mu\) | \(\implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle g * u = \left({f * \mu}\right) * u\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle g * u = f * \left({\mu * u}\right)\) | \(\displaystyle \) | \(\displaystyle \) | |||
| \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\implies\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle g * u = f\) | \(\displaystyle \) | \(\displaystyle \) |
Hence the result.
$\blacksquare$
Source of Name
This entry was named for August Ferdinand Möbius.
