莫比乌斯反演证明:

条件:$g(n)=\sum\limits_{d|n}f(d)$

求证:$f(n)=\sum\limits_{d|n}g(d)*\mu(\frac{n}{d})$

证明:(通过代换)

$$\begin{align}\sum\limits_{d|n}g(d)*\mu(\frac{n}{d})&=\sum\limits_{d|n}g(\frac{n}{d})*\mu(d)\\&=\sum\limits_{d|n}\mu(d)*\sum\limits_{i|\frac{n}{d}}f(i)\\&=\sum\limits_{d|n}\mu(d)*\sum\limits_{i*d|n}f(i)\\&=\sum\limits_{i|n}f(i)*\sum\limits_{d|\frac{n}{i}}\mu(d)\\&=f(n)\end{align}$$

解释一下，从第三步到第四步实际上是$i*d|n$不同枚举方式。

而最后一步用了$\sum\limits_{i|n} \mu(i)=\begin{cases}0,n>1\\1,n=1\end{cases}$

还有反演的另外一种表达形式，已知$g(n)=\sum\limits_{n|d}f(d)$，求证$f(n)=\sum\limits_{n|d}g(d)*\mu(\frac{d}{n})$

也证明一下:

$\sum\limits_{n|d}g(d)*\mu(\frac{d}{n})=\sum\limits_{k=1}^{\infty}\mu(k)\sum\limits_{kn|d}f(d)=\sum\limits_{n|d} f(d)\sum\limits_{k|\frac{d}{n}}\mu(k)=f(n)$