# Proof of Möbius inversion formula - the other direction

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.

• How about just doing it? Put the second into the first, and hack away.... Commented Jan 27, 2019 at 10:41
• @LordSharktheUnknown not sure how I would do that, sorry Commented Jan 27, 2019 at 10:54
• It's kind of hard to avoid using convolutions when there's one in the problem's statement. Commented Jan 27, 2019 at 10:57

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.