注：本节内容为《具体数学》(原书第二版) 第四章 数论 4.9 $\varphi$ 与 $\mu$ 的旁注。

P112 $\mu$ 函数为什么能递推？

先看定义：

$$
\boxed{\sum_{d\mid m}\mu(d)}=\boxed{[m=1]}
$$

$\mu(m)$ 之所以是递归式，是因为最初我们可以很轻松地确定：$\mu(1)=1$，之后随着 $m$ 值的增长，我们计算 $\mu(m)$ 时用到的值 $\mu(d)$ 一定有 $d < m$。故整个过程可以通过递推得到。

P113 莫比乌斯反演的证明

试证:

$$
g(m) = \sum_{d\mid m}f(d) \Leftrightarrow f(m)=\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right)
$$

证明：

若 $g(m) = \sum_{d\mid m}f(d)$，则

$$
\begin{aligned}
&\sum_{d \mid m} \mu(d) g\left(\frac{m}{d}\right) \\
&=\sum_{d \backslash m} \mu\left(\frac{m}{d}\right) g(d) \\
&=\sum_{d \backslash m} \mu\left(\frac{m}{d}\right) \sum_{k \backslash d} f(k) \\
&=\sum_{d \backslash m} \sum_{k \backslash d} \mu\left(\frac{m}{d}\right) f(k) \\
&=\sum_{k \backslash m} \sum_{d \backslash(m / k)} \mu\left(\frac{m}{k d}\right) f(k), \text{by equation (4.9)} \\
&=\sum_{k \backslash m} \sum_{d \backslash(m / k)} \mu(d) f(k) \\
&=\sum_{k \backslash m} f(k) \sum_{d \backslash(m / k)} \mu(d) \\
&=\sum_{k \backslash m} f(k)\left[\frac m k=1\right]=f(m)
\end{aligned}
$$

若 $f(m)=\sum_{d \backslash m} \mu(d) g\left(\frac{m}{d}\right)$，则

$$
\begin{aligned}
&\sum_{d\backslash m}f(d) \\
=&\sum_{d\backslash m} \sum_{k\backslash d} \mu\left(\frac d k\right) g\left(k\right) \\
=&\sum_{k\backslash m} \sum_{d\backslash (m/k)} \mu\left ( \frac {dk} {k} \right) g(k) \\
=&\sum_{k\backslash m} \sum_{d\backslash (m/k)} \mu(d) g\left (k\right) \\
=&\sum_{k\backslash m} g\left (k\right) \sum_{d\backslash (m/k)} \mu(d) \\
=&\sum_{k\backslash m} g\left (k\right) \left[\frac m k = 1\right] \\
=&\sum_{k\backslash m} g\left (k\right) \left[m = k\right] \\
=&g(m)
\end{aligned}
$$

Q.E.D.

此处也包含了习题 12 的证明。

P114 $\sum\Phi\left(\frac x d\right)$ 的含义

我们来考察下面的式子的含义:

$$
\sum_{d \geq 1} \Phi \left( \frac xd\right)
$$

其中

$$
\Phi(x) = \sum_{1 \leq k \leq x} \varphi(k)
$$

这个式子代表了 满足 $0\leq m < n \leq x$ 的基本分数 $\displaystyle\frac m n$的个数（既有最简分数，又有）。

为什么？我们不妨来逐项分析。同时，我们首先考虑 $x\in \mathbb Z$ 的情况。

$\displaystyle\Phi \left( \frac xd\right)$ 代表的是最大分母为 $\displaystyle \left \lfloor\frac xd \right\rfloor$ 的法里级数的个数减去 1 (那个 1/1)，也就是在所有满足条件的基本分数中被约分 $d$ 后的个数（因为法里级数都是最简分数）。

所以，我们只要穷举 $d \geq 2$，便能得到所有可以约分的情况下的被约分的非最简分数的个数。而当 $d = 1$，即 $\frac x d = x$ 时，得到的就是最简分数的个数，也就是法里级数的个数减去 1.

故

$$
\sum_{d \geq 1} \Phi \left( \frac xd\right)
$$

就代表了所有基本分数的个数。

接下来，我们来论证为什么 $x\in \mathbb R$ 结论仍然成立。注意到，我们这里唯一使用到 $x$ 的地方就是 $\displaystyle \left \lfloor\frac xd \right\rfloor$ 与 $1 \leq k \leq x$，我们不妨稍作改写，使之对整数仍然成立：

变为 $\displaystyle \left\lfloor\frac {\left\lfloor x\right\rfloor}d \right\rfloor$ 与 $1 \leq k \leq \lfloor x\rfloor$。可以发现，根据我们在第三章证明的性质：

$$
\left\lfloor\frac {\left\lfloor x\right\rfloor}d \right\rfloor = \left \lfloor\frac xd \right\rfloor
$$

以及 $k \in \mathbb Z$，我们可以发现所有关系依旧成立！所以 $x\in\mathbb R$ 的范围仍然是对的。

故

$$
\sum_{d \geq 1} \Phi \left( \frac xd\right) = \frac 1 2 \lfloor x \rfloor \lfloor 1+x \rfloor
$$

P115 更广泛的莫比乌斯反演

$$
g(x) = \sum_{d \geq 1} f\left(\frac x d\right) \Leftrightarrow f(x) = \sum_{d \geq 1} \mu(d) g\left(\frac xd\right)
$$

证明：

若 $g(x) = \sum_{d \geq 1} f\left(\frac x d\right)$，则

$$
\begin{aligned}
\sum_{d \geqslant 1} \mu(d) g(x / d) &=\sum_{d \geqslant 1} \mu(d) \sum_{k \geqslant 1} f(x / k d) \\
&=\sum_{d \geqslant 1} \sum_{k \geqslant 1} f(x / k d) \mu(d) \\
&=\sum_{d \geqslant 1} \sum_{k \geqslant 1} \sum_{m} f(x / m) \mu(d) [m=kd] \\
&=\sum_{m \geqslant 1} f(x / m) \sum_{d, k \geqslant 1} \mu(d)[m=k d] \\
&=\sum_{m \geqslant 1} f(x / m) \sum_{d \backslash m} \mu(d) \\
&=\sum_{m \geqslant 1} f(x / m)[m=1]=f(x)
\end{aligned}
$$

若 $f(x) = \sum_{d \geq 1} \mu(d) g\left(\frac xd\right)$，则

$$
\begin{aligned}
\sum_{d \geq 1} f\left(\frac x d\right) &= \sum_{d \geq 1} \sum_{k\geq 1} \mu(k) g(x/kd) \\
&=\sum_{d \geq 1} \sum_{k\geq 1} \sum_m \mu(k) g(x/m) [m=kd] \\
&=\sum_{m \geq 1}g(x/m)\sum_{d,k\geq 1}\mu(k)[m=kd] \\
&=\sum_{m \geq 1}g(x/m)\sum_{k\backslash m}\mu(k) \\
&=\sum_{m \geq 1}g(x/m)[m=1] \\ &=g(x) &\square
\end{aligned}
$$