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.