TAOCP 1.2.7 Exercise 8
Equation (8) gives \sum_{k=1}^{n}H_k=(n+1)H_n-n.
Section 1.2.7: Harmonic Numbers
Exercise 8. [HM18] Compare Eq. (8) with $\sum_{k=1}^{n}\ln k$; estimate the difference as a function of $n$.
Verified: yes
Solve time: 1m23s
Solution
Equation (8) gives
$$ \sum_{k=1}^{n}H_k=(n+1)H_n-n. $$
The analogous quantity for logarithms is
$$ \sum_{k=1}^{n}\ln k=\ln(n!). $$
Since
$$ H_n=\sum_{k=1}^{n}\frac1k, $$
the standard comparison between the harmonic series and the logarithm yields
$$ H_n=\ln n+\gamma+\delta_n, $$
where $\gamma$ is Euler's constant and $\delta_n\to0$ as $n\to\infty$.
Substituting into (8),
$$ \sum_{k=1}^{n}H_k =(n+1)(\ln n+\gamma+\delta_n)-n. $$
Hence
$$ \sum_{k=1}^{n}H_k-\sum_{k=1}^{n}\ln k =(n+1)(\ln n+\gamma+\delta_n)-n-\ln(n!). $$
To estimate this difference, use Stirling's formula
$$ \ln(n!) = n\ln n-n+\frac12\ln(2\pi n)+O!\left(\frac1n\right). $$
Therefore
$$ \begin{aligned} \sum_{k=1}^{n}H_k-\ln(n!) &=(n+1)\ln n+(n+1)\gamma+(n+1)\delta_n-n \ &\qquad-\left(n\ln n-n+\frac12\ln(2\pi n)+O!\left(\frac1n\right)\right) \ &=\ln n+(n+1)\gamma+(n+1)\delta_n -\frac12\ln(2\pi n) +O!\left(\frac1n\right). \end{aligned} $$
Since $\delta_n=O(1/n)$, we have
$$ (n+1)\delta_n=O(1), $$
and consequently
$$ \sum_{k=1}^{n}H_k-\ln(n!) = n\gamma+\frac12\ln n +\gamma-\frac12\ln(2\pi) +O(1). $$
A sharper estimate follows from
$$ H_n=\ln n+\gamma+\frac1{2n}+O!\left(\frac1{n^2}\right), $$
which gives
$$ (n+1)\delta_n =\frac12+O!\left(\frac1n\right). $$
Substituting,
$$ \sum_{k=1}^{n}H_k-\ln(n!) = n\gamma+\frac12\ln n +\gamma+\frac12-\frac12\ln(2\pi) +O!\left(\frac1n\right). $$
Thus the difference between the harmonic-number sum and its logarithmic analogue grows linearly with $n$, with leading term $n\gamma$:
$$ \boxed{ \sum_{k=1}^{n}H_k-\sum_{k=1}^{n}\ln k = n\gamma+\frac12\ln n +\gamma+\frac12-\frac12\ln(2\pi) +O!\left(\frac1n\right) }. $$
In particular,
$$ \sum_{k=1}^{n}H_k-\sum_{k=1}^{n}\ln k \sim n\gamma . $$
$$ \boxed{\sum_{k=1}^{n}H_k-\sum_{k=1}^{n}\ln k \sim n\gamma} $$