对于二项式反演和莫比乌斯反演, 众所周知的证明给我的印象是对着结论干, 感觉很不优美， 就想试试有没有其它办法
前置知识：指数型生成函数(EGF)和狄利克雷生成函数(DGF)的定义
二项式反演
- 内容
[g_n = sum_{i=0}^{n}inom{n}{i}f_iiff f_i = sum_{i = 0}^{n}(-1)^{n - i}inom{n}{i} g_i
]
- 证明
设 (f(x)) 为数列 f 的 EGF, (g(x)) 为数列 g 的 EGF, 则有
[egin{aligned}
g(x) &= e^xf(x)\
e^{-x}g(x) &= f(x)
end{aligned}
]
展开即可
莫比乌斯反演
- 内容
[F(n)=sum_{d|n}f(d)iff f(n)=sum_{d|n}mu(d)F(frac{n}{d})
]
- 证明
设 (M(x)) 为莫比乌斯函数的 DGF, (f(x)) 为 f 数列的 DGF, (F(x)) 为 F 数列的 DGF, 则有
[F(x) = zeta(x)f(x)\
F(x)zeta^{-1}(x) = f(x)
]
注意到
[frac{1}{zeta(x)} = M(x)
]
带回原式即可完成证明。