Mobius inversion formula
The Möbius Inversion Formula is a relation between pairs of arithmetic functions, each defined from the other by sums over divisors. Originally proposed by August Ferdinand Möbius in 1832, it has many uses in Number Theory and Combinatorics.
The Formula
Let and
be arithmetic functions and
denote the Möbius Function. Then it follows that
![$g(n)=\sum_{d|n}f(d)\leftrightarrow f(n)=\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu\left(\frac{n}{d}\right)g(d).$](http://latex.artofproblemsolving.com/e/1/4/e14cc6518c4c04a4846aa1c5fcba429b6de8b21f.png)
: Notice the double implication, so we have two directions to prove. We proceed with the proof of the backwards direction first. We have
![$\sum_{d|n}\mu(d)g\left(\frac{n}{d}\right)=\sum_{d|n}\mu(d)\sum_{c|\frac{n}{d}}f(c)=\sum_{cd|n}\mu(d)f(c)=\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d).$](http://latex.artofproblemsolving.com/4/2/6/426004de4e989c5a788701b1a5a5011cea826143.png)
To finish, we will use the fact that
![$\sum_{d|n}\mu(d)=1~\text{for}~n=1~,\sum_{d|n}\mu(d)=0~\text{for}~n>1.$](http://latex.artofproblemsolving.com/3/0/4/304a0e0f75100cb8309ea96377ae8d4bbf5d7ddd.png)
If we have then we have
![$\sum_{d|\frac{n}{c}}\mu(d)=\sum_{d|1}\mu(d)=1$](http://latex.artofproblemsolving.com/f/a/8/fa832e9018c0358652957cca0d4d3b5ac22d3f83.png)
and that if otherwise. Hence by considering
we get
![$\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d)=\sum_{c|n}f(c)=f(n).$](http://latex.artofproblemsolving.com/3/c/c/3cc513eafe165c6197b9de016999575e8abb49dd.png)
The first direction is satisfied, and now we must prove the second. We see that
![$\sum_{d|n}f(d)=\sum_{d|n}f\left(\frac{n}{d}\right)=\sum_{d|n}\sum_{c|\frac{n}{d}}\mu\left(\frac{n}{cd}\right)g(c)=\sum_{cd|n}\mu\left(\frac{n}{cd}\right)g(c)=\sum_{c|n}g(c)\sum_{d|\frac{n}{c}}\mu\left(\frac{n}{cd}\right)=g(n).$](http://latex.artofproblemsolving.com/d/1/c/d1c9c7b014598911eeb92ebcf3f794f9a2336776.png)
Both directions have been proven, which completes our work
Applications
One of the most common applications of the formula is by proving that
![$n=\sum_{d|n}\varphi(d)$](http://latex.artofproblemsolving.com/9/9/f/99fcdf6d532d7f8f31a81ef820b04c46668bac17.png)
While there are some common combinatorial and group theoretic arguments one could use, a Möbius Inversion Formula solution also suffices. Clearly by choosing and
the theorem is proven.