Möbius inversion formula

The Möbius inversion formula in number theory states that if g(n) and f(n) are arithmetic functions satisfying

$g(n)=\sum _{d\mid n}f(d)\quad {\mbox{for every integer }}n\geq 1$

then

$f(n)=\sum _{d\mid n}g(d)\mu (n/d)\quad {\mbox{for every integer }}n\geq 1$

where μ is the Möbius function and the sums extend over all positive divisors d of n.

The formula is also correct if f and g are functions from the positive integers into some abelian group.

In the language of convolutions (see multiplicative function), the inversion formula can also be expressed as

μ * 1 = ε.

An equivalent formulation of the inversion formula more useful in combinatorics is as follows: suppose F(x) and G(x) are complex-valued functions defined on the interval [1,∞) such that

$G(x)=\sum _{1\leq n\leq x}F(x/n)\quad {\mbox{ for all }}x\geq 1$

then

$F(x)=\sum _{1\leq n\leq x}\mu (n)G(x/n)\quad {\mbox{ for all }}x\geq 1.$

Here the sums extend over all positive integers n which are less than or equal to x.

The Möbius inversion treated above is the original Möbius inversion. When the partially ordered set of natural numbers ordered by divisibility one is replaced by other locally finite partially ordered sets, one has other Möbius inversion formulas; for an account of those, see incidence algebra.