莫比乌斯反演(三):莫比乌斯反演定理

莫比乌斯反演定理

定理

第一种形式的莫比乌斯反演

存在 $f(x)$ 和 $g(x)$ 是定义在非负整数域的函数,并且满足

式子等价于


第二种形式的莫比乌斯反演

莫比乌斯反演还存在另一种形式:


存在

式子等价于

证明

第一种形式的证明

简单朴素证明:

只需证右边 $\sum_{d|n}\mu(d)f(\frac{n}{d})$ 等于左边的 $g(n)$ 即可。

如上,$g(n)=\sum_{d|n}\mu(d)f(\frac{n}{d})$ 得证。

卷积证明:

证明参考:点击此链接
求证:

已知 $\mu$ 为莫比乌斯函数, $u$ 为乘法单位元, $e$ 为单位元。
它们存在以下三个性质:1. $u = \mu^{-1}$ 。2. $u*\mu=e$ 。3. $e*f=f$ 。
求证: $f = g * u \Leftrightarrow g = f*\mu$
先证: $f=g*u\Rightarrow g = f*\mu$

如上,$f(n) = \sum_{d|n}g(d) \Rightarrow g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})$ 得证。
再证: $g = f * \mu \Rightarrow f=g*u$

如上, $g = f * \mu \Rightarrow f=g*u$ 得证。
即 $f(n) = \sum_{d|n}g(d) \Leftrightarrow g(n) = \sum_{d|n}\mu(d)f(\frac{n}{d})$ 得证。

第二种形式的证明

简单朴素证明

求证 $f(n)=\sum_{n|d}g(d) \Leftrightarrow g(n)=\sum_{n|d}\mu(\frac{d}{n})f(d)$
令 $k={d\over n}$ ,

观察 $\sum_{n|i}g(i)\sum_{k|{i\over n}}\mu(k)$ ,当且仅当 ${i\over n}=1$,即 $i=n$ 时,$\sum_{k|{i\over n}}\mu(k)=1$,其余都是 $0$。因此

得证。