Möbius inversion

Question

The Möbius inversion formula says given two arithmetic functions $\hat{g}(k)$ and $g(k)$ related by $$\sum_{d\mid k}\hat{g}(d)=g(k)$$ Then $$\sum_{d\mid k}\mu(d)g\left(\frac{k}{d}\right)=\hat{g}(k)$$ Can someone give me a very elementary proof of this?

I don't know anything about analytic number theory, though I know the definition of the Möbius function, and have used it before with out ever reading to deeply into it for example: I know that, $\frac{x}{1-x}=x+x^2+x^3+x^4+\cdots$ And that if I subtract the even powers I get, $\frac{x}{1-x}-\frac{x^2}{1-x^2}=x+x^3+x^5+x^7+x^9+\cdots$ And then If I subtract the the powers that are multiples of 3 I get, $\frac{x}{1-x}-\frac{x^2}{1-x^2}-(\frac{x^3}{1-x^3}-\frac{x^6}{1-x^6})=x+x^5+x^7+x^{11}+\cdots$ Continuing in this matter one sees we are essentially yielding combinations of the original sum where the argument is a combination of distinct primes, and the coefficients are determined by weather or not the number of primes is even or odd. So by the definition of the Möbius function I can easily see, $\sum_{k=1}^\infty\frac{\mu(k)x^k}{1-x^k}=x$, although the first theorem I mentioned doesn't seem so obvious to me, and so I would appreciate a simple proof.

Answer 1

If you want a proof in the spirit of generating functions, we may use (formal) Dirichlet series.

We have the Euler product factorization

$$\zeta(s)=\prod_p\left(1-\frac{1}{p^s}\right)^{-1}$$

and hence

$$\frac{1}{\zeta(s)}=\prod_p\left(1-\frac{1}{p^s}\right)=\sum_{n=1}^\infty\frac{\mu(n)}{n^s}.$$

Set $g(n):=\sum\limits_{d\mid n}\hat{g}(d)$ and use the substitution $n=dm$ to obtain

$$G(s)=\sum_{n=1}^\infty \frac{g(n)}{n^s}=\sum_{n=1}^\infty\sum_{d\mid n}\hat{g}(d)n^{-s}=\left(\sum_{d=1}^\infty\frac{\hat{g}(d)}{d^s}\right)\left(\sum_{m=1}^\infty\frac{1}{m^s}\right)=\hat{G}(s)\zeta(s).$$

Multiply both sides by $\zeta(s)^{-1}$ to obtain

$$\hat{G}(s)=\sum_{n=1}^\infty\frac{\hat{g}(n)}{n^s}=\frac{1}{\zeta(s)}G(s)=\left(\sum_{d=1}^\infty\frac{\mu(d)}{d^s}\right)\left(\sum_{m=1}^\infty\frac{g(m)}{m^s}\right)=\sum_{n=1}^\infty\frac{1}{n^s}\sum_{dm=n}\mu(d)g(m).$$

Comparing coefficients gives the result.

Remark 1. Convergence is not an issue since we are working with formal Dirichlet series. We say a sequence $(\sum_{n=1}^\infty a_{n,m}n^{-s})_{m=1}^\infty$ of series converges to $\sum_{n=1}^\infty c_nn^{-s}$ as $m\to\infty$ if each sequence $(a_{n,m})_{m=1}^\infty$ converges to $c_n$ and (a much stronger condition) is eventually constant. This allows us to interpret many of the operations used above rigorously.

Remark 2. This is more or less the same proof as the usual, functional one (involving Dirichlet convolution), only that sequences are encoded as analytic (really, algebraic-number-theoretic) gadgets. Indeed, if $A(s)$ and $B(s)$ are Dirichlet series with coefficients $(a_n)_{n=1}^\infty$ and $(b_m)_{m=1}^\infty$ resp. then $A(s)B(s)$ has coefficients $(a\star b)_n$, the convolution of the two sequences. The utility here is that it is especially easy to see $(\mu\star1)=\delta$ and the associativity of $\star$ follows from associativity of the usual multiplication in the ring of formal Dirichlet series.

Answer 2

If $a(n)$ and $b(n)$ are two sequences, then define the convolution as $$(a \star b)(n) = \sum_{d \vert n} a(d) b(n/d)$$ First note that $$\sum_{d \vert n} \mu(d) = \sum_{d \vert n} \mu(n/d) = (1 \star \mu)(n) = \delta(n) = \begin{cases}1 & n=0\\ 0 & \text{otherwise} \end{cases} \,\,\,\,\,\,\,\, \text{(Why?)}$$ We have that $$\left(\hat{g} \star 1 \right)(n) = g(n)$$ Hence, we have $$\hat{g}(n) = (\hat{g} \star \delta)(n) = (\hat{g} \star(1 \star \mu))(n) = ((\hat{g} \star 1) \star \mu)(n) = (g \star \mu)(n)$$

EDIT

Let $n=p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, where $a_l \in \mathbb{Z}^+$. The only terms that contribute to $\sum_{d \vert n} \mu(d)$ is $d$'s of the form $d = p_1^{b_1} p_2^{b_2} \cdots p_k^{b_k}$ where $b_l \in \{0,1\}$. Half of these $d$'s will have $\mu(d)$ as $+1$ while the other half will have $\mu(d) = -1$.

Proving the associativity of $\star$ is a nice little exercise, which I will let you work out.