競技プログラミングをやっていると, たまに調和級数

\[H_n = \sum_{i=1}^n \frac{1}{i}\]

が$O(\log(n))$であることがでてきます.

この理由というと よく積分を使っているものが出てくるのですが, 高3の数学やってない人にはきついんじゃないかなー, と思ったので 積分を使わない方法を解説してみます.

自然数$n$に対して $2^{k} \le n < 2^{k + 1}$なる自然数$k$を取ります. すると

\[\begin{align*} H_n &= \frac1{1} + (\frac1{2} + \frac1{3}) + (\frac1{4} + \frac1{5} + \frac1{6} + \frac1{7}) + \cdots + (\frac1{2^{k-1}} + \frac1{2^{k-1} + 1} + \cdots + \frac1{2^k - 1}) + R \end{align*}\]

と書けます. ここで

\[R = \frac1{2^k} + \frac1{2^k + 1} + \cdots + \frac1{n}\]

です.

ここで,

\[\begin{align*} & \frac1{2} + \frac1{3} \le \frac1{2} + \frac1{2} = 1, \\ & \frac1{4} + \frac1{5} + \frac1{6} + \frac1{7} \le \frac1{4} + \frac1{4} + \frac1{4} + \frac1{4} = 1 \end{align*}\]

などを用いると

\[\begin{align*} H_n &\le \frac1{1} + (\frac1{2} + \frac1{2}) + (\frac1{4} + \frac1{4} + \frac1{4} + \frac1{4}) + \cdots + (\frac1{2^{k-1}} + \frac1{2^{k-1}} + \cdots + \frac1{2^{k-1}}) + R \\ &= 1 + 1 + \cdots + 1 + R \\ &= k + R. \end{align*}\]

これと同様にして $R \le 1$であることが分かるので, $H_n = O(k)$, すなわち$H_n = O(\log(n))$であることが分かりました.