Mobius Inversion Formula [Proof]

Question

Problem: Given $F(n)=\sum_{d|n}f(d),$ then show that $$f(n)=\sum_{d|n}\mu(d)F(n/d)=\sum_{d|n}\mu(n/d)F(n).$$

My attempt: I tried to prove $$f(n)=\sum_{d|n}\mu(d)F(n/d).$$ By considering an example, I observed the following $$f(6)=\mu(1)F(6)+\mu(2)F(3)+\mu(3)F(2)+\mu(6)F(1).$$ $$\Rightarrow \mu(1)\{f(1)+f(2)+f(3)+f(6)\}+\mu(2)\{f(1)+f(3)\}+\mu(3)\{f(1)+f(2)\}+\mu(6)\{f(1)\}$$ $$=f(1)\{\mu(1)+\mu(2)+\mu(3)+\mu(6)\}+f(2)\{\mu(1)+\mu(3)\}+f(3)\{\mu(1)+\mu(2)\}+f(6)\{\mu(1)\}.$$ It seems to me that $$\sum_{d|n}\mu(d)F(n/d)=\sum_{d|n}f(d)\sum_{r|\frac{n}{d}}\mu(r)=\sum_{d|n}\sum_{r|\frac{n}{d}}f(d)\mu(r).$$ When $n=6$ then$$ \sum_{d|n}\sum_{r|\frac{n}{d}}f(d)\mu(r)=f(1)\{\mu(1)+\mu(2)+\mu(3)+\mu(6)\}+f(2)\{\mu(1)+\mu(3)\}+f(3)\{\mu(1)+\mu(2)\}+f(6)\{\mu(1)\}.$$ But on rearranging we also that $$\sum_{d|n}\sum_{r|\frac{n}{d}}f(d)\mu(r)=\mu(1)\{f(1)+f(2)+f(3)+f(6)\}+\mu(2)\{f(1)+f(3)\}+\mu(3)\{f(1)+f(2)\}+\mu(6)\{f(1)\}.$$ Which motivates me to state that: $$\Rightarrow \sum_{d|n}\sum_{r|\frac{n}{d}}\mu(d)f(r)=\sum_{d|n}\mu(d)\sum_{r|\frac{n}{d}}f(r)=0.$$ I know this is incorrect. Please identify the mistake.

Answer 1

By way of enrichment here is a proof that the reader may want to examine. We seek to show that

$$f(n) = \sum_{d|n} \mu(n/d) \sum_{q|d} f(q).$$

Re-writing this in terms of $q$ we obtain for the RHS

$$\sum_{q|n} f(q) \sum_{p|n/q} \mu(n/q/p).$$

This is

$$\sum_{q|n} f(q) \sum_{p|n/q} \mu(p).$$

Recall that for $m\ge 2$

$$\sum_{p|m} \mu(p) = (1-1)^{\omega(m)} = 0 \quad \text{and} \quad \sum_{p|1} \mu(p) = 1.$$

Therefore all terms from the sum vanish except the one for $q=n$ and we have the end result

$$f(n).$$