莫比乌斯反演定理证明


我也不知道为啥要证明这玩意,但是我比较傻,看懂一遍之后怕忘了,所以还是写个博客。。

首先给出这么一个定义式:

$f(n)=\sum_{d\vert n}g(d)$

于是就有这么一个定理:

$g(n)=\sum_{d\vert n}\mu(d)\cdot f(\frac nd)$

话说回来这个$\mu(d)$就是莫比乌斯函数,定义是这样的

(1)若,那么

(2)若均为互异素数,那么

(3)其它情况下

于是有这样的性质

(1)对任意正整数

  

(2)对任意正整数

  

 

第一个性质其实还算好证。大概手玩一下组合数就行了。第二个我没推也没用上、、

下面是我xjb证的过程。。

首先要证$g(n)=\sum_{d\vert n}\mu(d)\cdot f(\frac nd)$,只要证明右边等于$g(n)$。

右式$=\sum_{d\vert n}(\mu(d)\cdot\sum_{e\vert\frac nd}g(e))$(定义式)

  $=\sum_{d\vert n}\sum_{e\vert\frac nd}(\mu(d)\cdot g(e))$(分配率)

稍微理解一下,发现其实是所有满足$(d\cdot e)\vert n$的二元组$(d,e)$之和。

于是可以交换前两个sum的位置即

$=\sum_{e\vert n}\sum_{d\vert\frac ne}\mu(d)\cdot g(e)$

$=\sum_{e\vert n}g(e)\cdot\sum_{d\vert\frac ne}\mu(d)$(分配率逆定律)

我们知道只有当$\frac ne=1$即$e=1$的时候后半部分才等于1,其他情况都为0。所以就等于$g(n)$。

得证。


 

upd

发现以前的证明不够优美啊。狄利克雷卷积的证明真的让人愉悦~

详见知乎高票回答https://www.zhihu.com/question/23764267

话说回来,莫比乌斯反演的第二种形式

$g(n)=\sum_{n\vert d}\mu(\frac dn)f(d)$

求一个证明啊qwq

智能推荐

注意!

本站转载的文章为个人学习借鉴使用,本站对版权不负任何法律责任。如果侵犯了您的隐私权益,请联系我们删除。



 
China Scenic Area
© 2014-2019 ITdaan.com 粤ICP备14056181号  

赞助商广告