A simple Blog for wyx I've been down the bottle hoping.
对于一类积性函数的总结
发表于: | 分类: Oi | 评论:0 | 阅读:68

我是来填坑的
我现在争取吧我会的证明都证明一遍造福一下以后的自己
首先是这个
$$\sum\limits_{d|n}^n{u(d)}=0,\text{前提是}n \ne 1$$
首先一个数$x$一定可以写成$x={p_1}^{a_1}\times{p_2}^{a_2}...\times{p_n}{a_n}$
然后上面那个次数大于2的都是0,就不用考虑这些数字了
然后思考剩下了一坨质数,这些质数互相组合
$$\sum\limits_{k=1}^n{C(n,k)\times(-1)^k}=\sum\limits_{k=1}^n{C(n,k)\times(-1)^k*1^{(n-k)}}=((-1)+1)^n=0$$
证完了

然后咱们来证一下莫比乌斯反演的式子
已知$F(x)=\sum\limits_{d|x}f(d)$
求证$f(x)=\sum\limits_{d|x}F(d)*u(\frac{x}{d})$

从下面的往上面的推一发就行了
$\sum\limits_{d|x}F(d)*u(\frac{x}{d})$
$=\sum\limits_{d|x}u(d)*F(\frac{x}{d})$这步可以理解为倒过来枚举
$=\sum \limits_{d|x}u(d)\times \sum\limits_{t|\frac{x}{d}}f(t)$ 把F带入即可
$=\sum \limits_{t|x}f(t)\times \sum\limits_{d|\frac{x}{t}}u(d)$ 这算是重点了,就是考虑一下一个$f(t)$会在什么时候被枚举到,然后我们把它提到前面来枚举一下
$\sum\limits_{d|\frac{x}{t}}u(d)$只有在$\frac{x}{t}=1$的时候才等于1,否则都是0,这个是上面的证明说完了的
然后说明只有$x=t$的时候这个东西有值等于$f(x)$
所以$f(x)=\sum\limits_{d|x}F(d)*u(\frac{x}{d})$
这个东西就证完了

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP