莫比乌斯反演证明:
条件:$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)$
最后一次更新于2020-05-25
0 条评论