note[16]
本题主要考察了欧拉函数 \(\varphi\) 和莫比乌斯函数 \(\mu\) 的互相转换。
题: \[ \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \varphi(i) \] 解: \[ \begin{aligned} \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \varphi(i) & = \lim _{n \rightarrow+\infty}\frac{1}{n^2} \sum_{i=1}^n\sum_{d=1}^i [\gcd(d,i)=1] \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n\sum_{d=1}^i\sum_{k \mid \gcd(d,i)}\mu(k) \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n\sum_{d=1}^i\sum_{k = 1}^n\mu(k)[k \mid \gcd(d,i)] \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{k = 1}^n\mu(k)\sum_{i=1}^n\sum_{d=1}^i[k \mid \gcd(d,i)] \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{k = 1}^n\mu(k)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}i \\[6pt]& =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \mu(i) \times \frac{\left\lfloor\frac{n}{i}\right\rfloor\cdot\left(\left\lfloor\frac{n}{i}\right\rfloor+1\right)}{2} \\[6pt]& =\frac{1}{2} \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \mu(i) \cdot\left(\frac{n}{i}\right)^2 \\[6pt]& =\frac{1}{2} \sum_{i \geq 1} \frac{\mu(i)}{i^2} \\[6pt]& =\frac{3}{\pi^2} \end{aligned} \] 提示:最后一步是狄利克雷生成函数,参考 生成函数 学习笔记 \[ \sum_{n=1}^{\infty} \frac{\mu(n)}{n^s}=\frac{1}{\zeta(s)} \]
其实还有一种推法,利用了 \(\varphi=\mu * \mathrm{id}\) 的性质 \[ \begin{aligned} \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \varphi(i) & =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \sum_{d \mid i} d \cdot \mu\left(\frac{i}{d}\right) \\[6pt] & =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \sum_{d = 1}^n d \cdot \mu\left(\frac{i}{d}\right) [d\mid i] \\[6pt] & =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{d = 1}^n\sum_{i=1}^n d \cdot \mu\left(\frac{i}{d}\right) [d\mid i] \\[6pt] & =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{d = 1}^n\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor} d \cdot \mu(i) \\[6pt] & =\lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{d = 1}^nd\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(i) \end{aligned} \] 我们观察 \(\mu(i)\) 是如何贡献的
n/n
...
1 2 3 ... n/2
1 2 3 ............... n/1
n=5
d=1 1
d=2 1
d=3 1
d=4 1 2
d=5 1 2 3 4 5
可以发现贡献就是这个 \[ \lim _{n \rightarrow+\infty} \frac{1}{n^2} \sum_{i=1}^n \mu(i) \times \frac{\left\lfloor\frac{n}{i}\right\rfloor\cdot\left(\left\lfloor\frac{n}{i}\right\rfloor+1\right)}{2} \] 后面一样的。
参考文献&致谢:
[0] 感谢 Roundgod 的帮助!
[1] https://www.cnblogs.com/CDOI-24374/p/18109342
[2] https://en.wikipedia.org/wiki/M%C3%B6bius_function
题外话:
以及,(WolframAlpha)真的太逊啦!