Understanding the proof of Möbius inversion formula

Question

I am trying to understand one step in the proof of the Möbius inversion formula.

The theorem is

Let $f(n)$ and $g(n)$ be functions defined for every positive integer $n$ satisfying $$f(n) = \sum_{d|n}g(d)$$ Then, g satisfies $$g(n)=\sum_{d|n}\mu(d) f(\frac{n}{d})$$

The proof is as follows:

We have $$\sum_{d|n}\mu(d)f(\frac{n}{d}) = \sum_{d|n}\mu(\frac{n}{d})f(d) = \sum_{d|n}\mu(\frac{n}{d}) \sum_{d'|d}g(d') = \sum_{d'|n}g(d')\sum_{m|(n/d')}\mu(m)$$ Where in the last term, the inner sum on the right hand side is $0$ unless $d'=n$.

My question is: how do we get the last equation? I don't really understand how the author interchanges the summation signs. Thanks for any help!

Answer 1

First, considering the sum \begin{align*} \sum_{d|n}\mu(\frac{n}{d})\sum_{m|d}g(m), \end{align*} let's take a look into the indices $$ n=\frac{n}{d}d=\frac{n}{d}\frac{d}{m}m=khm, $$ with $$ \frac{n}{d}=k, \frac{d}{m}=h. $$ Thus, we have

\begin{align*} \sum_{d|n}\mu(\frac{n}{d})\sum_{m|d}g(m) &=\sum_{dk=n}\mu(k)\sum_{hm=d}g(m)\\ &=\sum_{khm=n}\mu(k)g(m)\\ &=\sum_{mkh=n}g(m)\sum_{kh=\frac{n}{m}}\mu(k)\\ &=\sum_{m|n}g(m)\sum_{k|\frac{n}{m}}\mu(k)\\ &=\sum_{m|n}g(m)[\frac{m}{n}]=g(n). \end{align*} If you are reading Apostol, then in his book's convention, we can see that we're in fact doing the convolution $$ f*\mu=(g*U)*\mu=g*(U*\mu)=g*I=g, $$ with $U(n)=1$ and $I(n)=[\frac{1}{n}].$

The tricky part here is that there are really three arithmetic functions convoluting with each other, namely, $f$, $g$ and $U.$

Answer 2

The switch of summation is just a change of indices (which does not really use what $\mu$ is):

$$\sum_{d\mid n}\mu\left(\frac nd\right)\sum_{d'\mid d}g(d')=\sum_{d'\mid d \mid n}g(d')\mu\left(\frac nd\right)$$

Now you observe that, if $d',\ d$ are divisors of $n$, then $d'\mid d$ if and ony if $\frac n{d}\mid \frac n{d'}$. For the same reason, $m\mid \frac{n}{d'}$ if and only if $d'\mid \frac nm\mid n$.

So, if you set $m:=\frac nd$ and sum over a fixed $d'$, you get

$$\sum_{d'\mid d \mid n}g(d')\mu\left(\frac nd\right)=\sum_{d'\mid n}g(d')\sum_{m\mid \frac n{d'}}\mu(m)$$