莫比乌斯反演公式的证明
公式(形式一)
$$F(n)=\sum_{d|n} f(d)=>f(n)=\sum_{d|n} \mu(d)F(\frac{n}{d})$$
证明
$$我们要证明f(n)=\sum_{d|n} \mu(d)F(\frac{n}{d})可以先从\sum_{d|n} \mu(d)F(\frac{n}{d})来推OwO$$
第一步:
$$\sum_{d|n} {\mu(d)F(\frac{n}{d})}=\sum_{d|n} {\mu(d)\sum_{k|\frac{n}{d}}f(k)}$$
$这步应该十分显然,就是在左边的基础上套用F(n)的定义$
第二步:
$$\sum_{d|n} {\mu(d)\sum_{k|\frac{n}{d}}f(k)}=\sum_{k|n} {f(k)\sum_{d|\frac{n}{k}}\mu(d)}$$
这步有点难理解,因为这是证明的精髓所在
$仔细解释下,就是说把f(k)个\mu(d)转换成了\mu(d)个f(k)$
这是因为k和d是等价的…
这个解释,苍白无力…
$仔细想,每一个f(k)对应了一堆\mu(d)$
$然后,每个对应的\mu(d)也可以对应出相应的f(k)$
脑补一下,其实还是很有道理的XD
第三步:
$$\sum_{k|n} {f(k)\sum_{d|\frac{n}{k}}\mu(d)}=f(n)$$
这一步应用了一个小定理
$$\sum_{d|n}\mu(d)=\begin{cases}1, & \text{n=1} \[2ex]0, & \text{n≠1}\end{cases}$$
$所以仅当k=n时\sum_{d|\frac{n}{k}}\mu(d)=1$
于是我们就得到了答案!!!
把过程连起来写就是这样的:
$$\sum_{d|n} {\mu(d)F(\frac{n}{d})}=\sum_{d|n} {\mu(d)\sum_{k|\frac{n}{d}}f(k)}=\sum_{k|n} {f(k)\sum_{d|\frac{n}{k}}\mu(d)}=f(n)$$
证毕~~~
公式（形式二）
$$F(n)=\sum_{n|d} f(d)=>f(n)=\sum_{d|n} \mu(\frac{d}{n})F(d)$$
证明
$$同理，我们还是可以从f(n)=\sum_{d|n} \mu(\frac{d}{n})F(d)的左边，\sum_{d|n} \mu(\frac{d}{n})F(d)来推OwO$$