关于莫比乌斯函数性质的证明

关于上式有人问我不卷积怎么证，真是个好问题。

首先 时自算该式成立，

然后讨论 的情况。

---

下证

当 显然成立。

当 为奇数，总有 为奇数与偶数一一对应，则差为0.

当 为偶数时，

令 表示集合大小为 时选奇数个的情况， 表示集合大小为 时在其中选偶数个的情况。

当 为奇数时，，，且有 ，此时 ；

当 为偶数时，二分合并即可。

---

，

令 ，

设 的一个因数为 ，

设 。

1、若

其另一因数为 ，

此时 为奇数，

当 为奇数，，；当 为偶数，，。

。

2、若

将 分为 类:

1.；
2. 且 ；
3. 且 ；

第一种放着不管。

第二种情况，当且仅当 存在。显然在 时，。

第三种情况，只关心 即可。

当 为奇数时 ；当 为偶数时 。

而总有 为奇数情况比偶数情况多 。

即三种情况 和为 ，最后加上 。

3、若

此时 为偶数，

当 为奇数时，有 ；

当 为偶数时，有 。

总有 为奇数情况比偶数情况多 。

故 ，最后加上 。