调和级数的渐进表示

令 \(H_n\) 为第 n 项调和数

\[ H_n=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i} \]

证明 \(H_n\) 是 \(O(\log n)\) 的

证明 如下图所示:

img

\(\sum_{i=1}^{n}\frac{1}{i}\)可以看作图中蓝色阴影的面积; 而橙色部分的面积则可以看作函数 \(y=\frac{1}{x}\) 的积分 \(\int_{0}^{n}\frac{1}{x}\mathrm{d}x\). 因此有

\[ \sum_{i=2}^{n}\frac{1}{i}\lt \int_{0}^{n}\frac{1}{x}\mathrm{d}x=\ln n \]

\[ \sum_{i=1}^{n}\frac{1}{i}\lt \ln n + 1 = O(\log n) \]

证毕.