TAOCP 1.2.7 Exercise 4

Exercise 4. [10] Decide which of the following statements are true for all positive integers $n$:

Verified: no
Solve time: -

Statement 1 is false, since $H_1=1>\ln 1=0$.

Statement 2 is true for all positive integers $n$. Since $1/x$ is decreasing on $[1,n]$,

$$ \int_k^{k+1}\frac{dx}{x}<\frac{1}{k} \qquad (1\le k\le n-1). $$

Summing these inequalities gives

$$ \int_1^n\frac{dx}{x} < \sum_{k=1}^{n-1}\frac{1}{k} = H_n-\frac1n < H_n. $$

Therefore

$$ \ln n<H_n. $$

Statement 3 is false for all positive integers $n$. By the definition of Euler's constant,

$$ \gamma=\lim_{m\to\infty}(H_m-\ln m). $$

Hence $H_n-\ln n$ approaches $\gamma$ as $n\to\infty$. If $H_n>\ln n+\gamma$ were true for every $n$, then

$$ H_n-\ln n>\gamma $$

for every $n$, contradicting the fact that the sequence converges to $\gamma$. Therefore statement 3 cannot hold for all $n$.

Thus the correct classification is

$$ \boxed{\text{1 false,\quad 2 true,\quad 3 false.}} $$