Exercise 4.3.4 (New proof of the converse of Möbius inversion Theorem)

Proof.

As in Theorem 4.9, we suppose that

We define for every positive integer $n$,

By Theorem 4.8 (Möbius inversion formula), we obtain

The comparison of (1) and (2) gives for all positive integers $n$,

For $n=1$, we obtain ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid 1}\mu (d)F(n∕d)=\mu (1)F(1)=F(1)$, and similarly ${\sum <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid 1}\mu (d)G(n∕d)=1$. Then (3) shows that $F(1)=G(1)$.

Reasoning by strong induction, suppose that for some positive integer $n$

is true. Then, by (3),

If $d\mid n$ and $d\ne 1$, then $n∕d<n$. The induction hypothesis $𝒫(n)$ shows that $F(n∕d)=G(n∕d)$, thus

Then the equalities (4) and (5) give $F(n)=G(n)$, so $𝒫(n+1)$ is true, and the induction is done, so $𝒫(n)$ is true for every $n\ge 1$. Therefore

This proves Theorem 4.9 anew.

If $f(n)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n}\mu (d)F(n∕d)$for every positive integer $n$, then $F(n)={\sum <!--\; FUNCTION\; APPLICATION\; -->}_{d\mid n}f(d)$. □