Proof of Möbius inversion formula - the other direction

Question

The Möbius inversion formula states that if we define $f$ as $$f(m)=\sum_{d|m}g(d)$$ then $$g(m)=\sum_{d|m}f\left(\frac md\right)\mu(d)$$

We know that the other direction is also true: if we define $g$ as above, then $f$ also satisfies the above.

I've searched for the proof, but failed to find any that does not rely on convolutions. My question is whether there is a proof that relies on manipulating sums that proves the second direction of the theorem.

Answer 1

We assume \begin{align*} g(m)=\sum_{d|m}f\left(\frac md\right)\mu(d)\tag{1} \end{align*} and show the validity of \begin{align*} f(m)=\sum_{d|m}g(d)\tag{2} \end{align*}

It is convenient to use the unit-function $u$ defined as $u(n)=1, n\geq 1$.

We start with the right-hand side of (2) and obtain \begin{align*} \color{blue}{\sum_{m|n}g(m)}&=\sum_{m|n}\left(\sum_{d|m}f\left(\frac {m}{d}\right)\mu(d)\right)u\left(\frac{n}{m}\right)\tag{3}\\ &=\sum_{a\cdot m=n}\left(\sum_{b\cdot d=m}f(b)\mu(d)\right)u(a)\\ &=\sum_{a\cdot b\cdot d=n}f(b)\mu(d)u(a)\\ &=\sum_{b\cdot m=n}f(b)\left(\sum_{a\cdot d=m}\mu(d)u(a)\right)\\ &=\sum_{m|n}f\left(\frac{n}{m}\right)\left(\sum_{d|m}\mu(d)u\left(\frac{m}{d}\right)\right)\\ &=\sum_{m|n}f\left(\frac{n}{m}\right)\sum_{d|m}\mu(d)\\ &=\sum_{m|n}f\left(\frac{n}{m}\right)\left\lfloor\frac{1}{m}\right\rfloor\tag{4}\\ &\,\,\color{blue}{=f(n)}\tag{5} \end{align*}

and the claim (2) follows.

Comment:

• In (3) we use the identity (1) and multiply for convenience only with $1=u\left(\frac{n}{m}\right)$.

• In (4) we use the identity $\sum_{d|m}\mu(d)=\left\lfloor\frac{1}{m}\right\rfloor=\begin{cases}1&m=1\\0&m>1\end{cases}$.

• In (5) we obtain $f(n)$ since all other summands with $m>1$ in (4) give zero.

Note: We can omit the usage of $u$ in the derivation, but this might reduce readability.