莫比乌斯反演定理的证明。
p s : ps: ps:初学给自己做个笔记，怕以后忘了。
前置知识：莫比乌斯函数 μ \mu μ的两个性质：
1. ∑ d ∣ n μ ( d ) = [ n = = 1 ] 1.\sum\limits_{d|n}\mu(d)=[n==1] 1.d∣n∑μ(d)=[n==1]
2. ∑ d ∣ n μ ( d ) d = φ ( n ) n 2.\sum\limits_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n} 2.d∣n∑dμ(d)=nφ(n) （这里证明用不到)
定理：若有定义在 N + N^+ N+上的函数 F ( n ) , f ( n ) F(n),f(n) F(n),f(n)满足关系：
F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum\limits_{d|n}f(d) F(n)=d∣n∑f(d)，则有： f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum\limits_{d|n}\mu(d)F(\dfrac{n}{d}) f(n)=d∣n∑μ(d)F(dn)
证明：我们只需证上述等式右边等于左边即可。
∑ d ∣ n μ ( d ) F ( n d ) \sum\limits_{d|n}\mu(d)F(\dfrac{n}{d}) d∣n∑μ(d)F(dn)
= ∑ d ∣ n μ ( d ) ∑ e ∣ n d f ( e ) \sum\limits_{d|n}\mu(d)\sum\limits_{e|\frac{n}{d}}f(e) d∣n∑μ(d)e∣dn∑f(e) （定义) (1)
= ∑ d ∣ n ∑ e ∣ n d μ ( d ) f ( e ) \sum\limits_{d|n}\sum\limits_{e|\frac{n}{d}}\mu(d)f(e) d∣n∑e∣dn∑μ(d)f(e) (分配律) (2)
= ∑ e ∣ n ∑ d ∣ n e μ ( d ) f ( e ) \sum\limits_{e|n}\sum\limits_{d|\frac{n}{e}}\mu(d)f(e) e∣n∑d∣en∑μ(d)f(e) ( e , d e,d e,d的地位是可交换的) (3)
= ∑ e ∣ n f ( e ) ∑ d ∣ n e μ ( d ) \sum\limits_{e|n}f(e)\sum\limits_{
{d|\frac{n}{e}}}\mu(d) e∣n∑f(e)d∣en∑μ(d) (结合律) (4)
= f ( n ) f(n) f(n) ( μ \mu μ性质1) (5)
证毕。
如果这里还是看不懂请看下面。
对于 ( 2 ) → ( 3 ) (2)\rightarrow(3) (2)→(3)的解释：
因为 e ∣ n d ⇔ e d ∣ n e|\dfrac{n}{d}\Leftrightarrow ed|n e∣dn⇔ed∣n
可以理解为对每个 n n n的因子 d d d求出所有满足 e d ∣ n ed|n ed∣n的 e e e,即二元组 ( d , e ) (d,e) (d,e)的个数。
举个例子： n = 6 n=6 n=6.
d = 1 , e = { 1 , 2 , 3 , 6 } d=1,e=\{1,2,3,6\} d=1,e={
1,2,3,6}
d = 2 , e = { 1 , 3 } d=2,e=\{1,3\} d=2,e={
1,3}
d = 3 , e = { 1 , 2 } d=3,e=\{1,2\} d=3,e={
1,2}
d = 6 , e = { 1 } d=6,e=\{1\} d=6,e={
1}
因为 e , d e,d e,d都是 n n n的因子，所以地位等价。
即条件可以改为 d ∣ n e ⇔ d e ∣ n d|\dfrac{n}{e}\Leftrightarrow de|n d∣en⇔de∣n
每个 n n n的因子 e e e求出所有满足 d e ∣ n de|n de∣n的 e e e,即二元组 ( e , d ) (e,d) (e,d)的个数。
e = 1 , d = { 1 , 2 , 3 , 6 } e=1,d=\{1,2,3,6\} e=1,d={
1,2,3,6}
e = 2 , d = { 1 , 3 } e=2,d=\{1,3\} e=2,d={
1,3}
e = 3 , d = { 1 , 2 } e=3,d=\{1,2\} e=3,d={
1,2}
e = 6 , d = { 1 } e=6,d=\{1\} e=6,d={
1}
( 4 ) → ( 5 ) (4)\rightarrow(5) (4)→(5)的解释：
显然当 n e ≠ 1 \dfrac{n}{e}\neq1 en=1时， ∑ d ∣ n e μ ( d ) = 0 \sum\limits_{
{d|\frac{n}{e}}}\mu(d)=0 d∣en∑μ(d)=0。
只有当 n e = 1 → e = n \dfrac{n}{e}=1\rightarrow e=n en=1→e=n时， ∑ d ∣ n e μ ( d ) = 1 \sum\limits_{
{d|\frac{n}{e}}}\mu(d)=1 d∣en∑μ(d)=1
即 ∑ e ∣ n f ( e ) ∑ d ∣ n e μ ( d ) \sum\limits_{e|n}f(e)\sum\limits_{
{d|\frac{n}{e}}}\mu(d) e∣n∑f(e)d∣en∑μ(d)= f ( n ) × 1 = f ( n ) f(n)\times 1=f(n) f(n)×1=f(n)。
卷积证明见置顶回答
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/220753.html原文链接：https://javaforall.net
