计算机程序设计艺术

背景：

在调和级数\(H_n\)的基础上，我们已清楚关于其求和的基本等式，即\(\sum_{k=1}^{n}H_k = (n+1)H_n -n\)。另一方面，我们也了解到调和级数与对数函数的一个大致关系，即\(H_n = lnn + \gamma + \frac{1}{2n}-\frac{1}{12n^2}+\frac{1}{120n^4}-\epsilon\)

问题：

对应调和级数的求和\(\sum_{k=1}^{n} H_n\)，可构造关于对数的求和\(\sum_{k=1}^{n}lnk\)，计算两者的差值及差值随着n的变化情况。

解构：

对问题中两求和的差值展开解析如下：

$$
\begin{align}
\sum_{k=1}^{n} H_k – \sum_{k=1}^{n}lnk
&= (n+1)H_n-n-\sum_{k=1}^{n}lnk \\
&= (n+1)\sum_{k=1}^{n}\frac{1}{k}-\sum_{k=1}^{n}lnk-n \\
&= \sum_{k=1}^{n}\left( \frac{n+1}{k}-lnk \right)-n
\end{align}
$$

记\(\phi(k) = \frac{n+1}{k}-lnk \)，则\(\sum_{k=1}^{n} \phi(k)\)可视作积分\(\int_{x=1}^{n} \phi(x)\)的一个估计值，反过来，亦可用积分值作为离散求和的估计值，如下：

$$
\begin{align}
\sum_{k=1}^{n} \phi(k) &\approx
\int_{x=1}^{n} \phi(x) \\
&= \int_{x=1}^{n} \frac{n+1}{x}-lnx \\
&= (n+1)lnx\Big|_1^n – \left( xlnx-x \right) \Big|_1^n \\
&= (n+1)lnn – nlnn+n – 1 \\
&= lnn+n-1
\end{align}
$$

因此，可以得到待求差值如下：

$$
\begin{align}
\sum_{k=1}^{n} H_k – \sum_{k=1}^{n}lnk
&=\sum_{k=1}^{n}\left( \frac{n+1}{k}-lnk \right)-n \\
&= \sum_{k=1}^{n} \phi(k)-n \\
&= lnn-1
\end{align}
$$