Consider the partial sum of the divergent Harmonic series $H_n = \sum\limits_{k = 1}^{n}\frac{1}{k}$. I recently saw a question which required finding out the asymptotic bounds of $H_n$. Now, I could not find any bound closer than $O(n)$. So I looked up the series and found this Wikipedia article which says that $H_n – \ln n$ approaches a constant (the Euler–Mascheroni constant). This clearly shows that $H_n = \Theta(\log n)$.
However, considering the question was in an beginners undergraduate algorithms course in CS, I was wondering if there is a simpler proof of this? Is there some clever proof requiring elementary mathematics to show $H_n = \Theta(\log n)$?
PS: This is not homework in the sense that it is not my homework, and the actual question does not ask for a proof, but rather asks a lot of functions to be arranged asymptotically.
Best Answer
$$ f(n) = H_n - \log n $$ starts a little high ($f(1) = 1$) and (strictly) decreases. $$ g(n) = H_n - \log (n+1) $$ starts a little low ($g(1) = 1 - \log 2$) and (strictly) increases. As $$ (f(n) - g(n)) \rightarrow 0 $$ they share a common limit. The common limit is called $\gamma,$ with $$ \gamma \approx 0.5772156649\ldots $$ So $$ H_n > \gamma + \log n, $$ $$ H_n < \gamma + \log (n+1), $$ together $$ \gamma + \log n < H_n < \gamma + \log (n+1). $$
======================
======================
This additional material is my answer to a question that was deleted by the person who posted it, https://math.stackexchange.com/questions/1432576/how-can-i-get-alpha-and-beta-numerically-euler-constant
Now that you know that the thing converges to a constant, you might want to know how to calculate that constant quickly to several decimal places. Of course, it is in many books and websites. Anyway, the sequence below obviously has the same limit, but the adjustments make it converge to $\gamma$ quickly. Alternatively, you can take $\gamma$ to $50$ digits and use this for very good accuracy in approximating $H_n.$
From two pages in Abramowitz and Stegun on the digamma function, especially formula 6.3.18 on page 259, which leads to $$ \scriptsize H_n = \gamma + \log n + \frac{1}{2n} - \frac{1}{12 n^2} + \frac{1}{120 n^4} - \frac{1}{252 n^6} + \frac{1}{240 n^8} - \frac{1}{132 n^{10}} + \frac{691}{32760 n^{12}} - \frac{1}{12 n^{14}} + \frac{3617}{8160 n^{16}} + O ( n^{-18}) $$
===========================================
The first few Bernoulli numbers are in table 23.1 on page 809 the column labelled $0.$ To start the whole thing you need the background on pages 255-259, especially integer values in 6.3.2 and recurrence in 6.3.5.
I wrote this out in C++ with GMP. The simple way to get decimal output is to use the direct conversion to C++ double, that means about sixteen decimal places can be expected to be correct. Turns out pretty well. I will put the program after, it is short.