Simple proof of showing the Harmonic number $H_n = \Theta (\log n)$
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.
$$ 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). $$
======================
n f g
1 1 0.3068528194400547
2 0.8068528194400547 0.4013877113318903
3 0.7347210446652236 0.4470389722134426
4 0.6970389722134425 0.4738954208992326
5 0.6738954208992328 0.4915738641052782
6 0.6582405307719448 0.5040898509446864
7 0.6469469938018292 0.5134156011773066
8 0.6384156011773066 0.5206325655209232
9 0.6317436766320343 0.526383160974208
10 0.6263831609742081 0.5310729811698832
11 0.621982072078974 0.5349706950893443
12 0.6183040284226777 0.5382613207491413
13 0.6151843976722184 0.5410764255184966
14 0.6125049969470682 0.5435121254601167
15 0.6101787921267836 0.5456402709892124
16 0.6081402709892124 0.5475156491727776
17 0.6063391785845421 0.5491807647445934
18 0.6047363203001488 0.550669099029873
19 0.6033006779772416 0.5520073835896911
20 0.602007383589691 0.5532172194202589
21 0.6008362670393064 0.5543162514044135
22 0.599770796858959 0.5553190342881251
23 0.5987972951576905 0.5562376807388946
24 0.5979043474055611 0.5570823528853059
25 0.597082352885306 0.5578616397320247
26 0.5963231781935631 0.558582850210716
27 0.5956198872477532 0.5592522430768784
28 0.594966528791164 0.5598752089798938
29 0.5943579676005833 0.560456415924902
30 0.5937897492582352 0.5609999264352443
31 0.5932579909513738 0.5615092926367935
32 0.5927592926367935 0.5619876339700398
33 0.5922906642730701 0.562437701123389
34 0.5918494658292712 0.5628619289560189
35 0.5914333575274474 0.563262480560751
36 0.5910402583385287 0.5636412841504143
37 0.5906683111774415 0.5640000640952801
38 0.5903158535689642 0.5643403671657036
39 0.5899813928067291 0.5646635848224393
40 0.5896635848224396 0.564970972232068
41 0.5893612161345071 0.5652636645554466
42 0.5890731883649704 0.5655426909547763
43 0.5887985049082647 0.5658089866835659
44 0.5885362594108384 0.5660634035587798
45 0.588285625781002 0.5663067190622267
46 0.588045849497009 0.5665396442760454
47 0.587816240020726 0.5667628308228936
48 0.5875961641562266 0.566976876953491
49 0.5873850402187969 0.5671823329012774
50 0.587182332901277 0.5673797056050973
51 0.5869875487423521 0.5675694628852506
52 0.5868002321160197 0.5677520371453252
53 0.5866199616736273 0.5679278286614747
54 0.5864463471799929 0.5680972085117963
55 0.5862790266936149 0.5682605211909366
56 0.5861176640480799 0.5684180869486789
57 0.5859619465978013 0.5685702038859322
58 0.5858115831962774 0.5687171498369772
59 0.58566630237935 0.5688591840629689
60 0.5855258507296355 0.5689965487784249
61 0.5853899914013755 0.5691294705295952
62 0.5852585027876601 0.569258161441219
63 0.5851311773142348 0.5693828203460957
64 0.5850078203460957 0.5695036338101304
65 0.5848882491947457 0.5696207770639573
66 0.5847722922154729 0.5697344148509323
67 0.584659787985261 0.5698447022001203
68 0.5845505845530614 0.5699517851319088
69 0.5844445387550973 0.5700558013029976
70 0.5843415155887118 0.5701568805967554
71 0.5842413876390093 0.5702551456642695
72 0.5841440345531588 0.5703507124208229
73 0.5840493425578088 0.5704436905020303
74 0.5839572040155434 0.5705341836834027
75 0.5838675170167363 0.5706222902667157
76 0.5837801850035582 0.5707081034362054
77 0.5836951164232185 0.5707917115873107
78 0.5836122244078235 0.5708731986303937
79 0.583531426478495 0.5709526442716348
80 0.583452644271635 0.5710301242730779
81 0.5833758032854236 0.5711057106936093
82 0.5833008326448283 0.5711794721124835
83 0.583227664883568 0.5712514738368524
84 0.5831562357416142 0.5713217780946114
85 0.5830864839769643 0.5713904442137729
86 0.5830183511905171 0.5714575287894412
87 0.5829517816630041 0.5715230858393814
88 0.5828867222030181 0.5715871669490846
89 0.5828231220052646 0.5716498214071395
90 0.5827609325182506 0.5717110963316655
91 0.5827001073206765 0.5717710367884862
92 0.5826406020058778 0.5718296859016622
93 0.5825823740737052 0.5718870849569572
94 0.5825253828292974 0.5719432734987605
95 0.5824695892882338 0.5719982894209384
96 0.5824149560876054 0.5720521690520588
97 0.5823614474025742 0.5721049472353851
98 0.5823090288680385 0.5721566574040206
99 0.5822576675050309 0.5722073316515295
100 0.5822073316515293 0.5722570007983612
101 0.5821579908973711 0.5723056944543594
102 0.5821096160229868 0.5723534410776222
103 0.5820621789417003 0.5724002680299634
104 0.5820156526453484 0.5724462016291977
105 0.5819700111530072 0.5724912671984634
106 0.581925229462614 0.572535489112775
107 0.581881283505298 0.5725788908429845
108 0.581838150102244 0.5726214949973201
109 0.5817958069239253 0.5726633233606527
110 0.5817542324515615 0.5727043969316437
111 0.581713405940653 0.5727447359578927
112 0.5816733073864638 0.5727843599692177
113 0.5816339174913419 0.572823287809187
114 0.5815952176337487 0.572861537664994
115 0.5815571898389075 0.5728991270957929
116 0.5815198167509655 0.5729360730595741
117 0.5814830816065826 0.5729723919386739
118 0.5814469682098607 0.5730080995639961
119 0.5814114609085339 0.5730432112380173
120 0.581376544571351 0.5730777417566559
121 0.581342204566573 0.5731117054300576
122 0.5813084267415329 0.573145116102372
123 0.5812751974031847 0.5731779871705653
124 0.5812425032995974 0.573210331602333
125 0.581210331602333 0.5732421619531562
126 0.5811786698896642 0.5732734903825508
127 0.5811475061305823 0.5733043286695565
128 0.5811168286695565 0.5733346882275014
129 0.5810866262119976 0.5733645801180873
130 0.581056887810395 0.5733940150648259
131 0.5810276028510858 0.5734230034658665
132 0.5809987610416243 0.5734515554062414
133 0.5809703523987224 0.5734796806695648
134 0.5809423672367291 0.573507388749211
135 0.5809147961566181 0.5735346888589955
136 0.5808876300354665 0.5735615899433936
137 0.5808608600163866 0.5735881006873068
138 0.5808344774989006 0.5736142295254136
139 0.5808084741297301 0.5736399846511175
140 0.5807828417939747 0.5736653740251106
141 0.5807575726066708 0.5736904053835784
142 0.5807326589047054 0.5737150862460588
143 0.5807080932390655 0.5737394239229722
144 0.5806838683674168 0.573763425522843
145 0.5806599772469807 0.5737870979592187
146 0.5806364130277116 0.5738104479573117
147 0.5806131690457473 0.5738334820603687
148 0.5805902388171257 0.5738562066357815
149 0.5805676160317548 0.5738786278809582
150 0.580545294547625 0.5739007518289565
======================
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}) $$
// n = 5 : 0.57721566490. Correct Truncated at 11.
// 137/60 - 120498003502669867/1246362304687500000 - log(5)
// n = 20 : 0.5772156649015328606065. Correct Truncated at 22.
// 55835135/15519504 - 132712185803482804044308617/5353085337600000000000000000 - log(20)
// The numerical value of the Euler–Mascheroni constant, to 50 decimal places, is
// 0.57721566490153286060651209008240243104215933593992
===========================================
n H_n Resulting estimate of gamma. 16th decimal place a bit random
1 1 0.2013580781963136
2 3/2 0.5772116186141515
3 11/6 0.5772156606867217
4 25/12 0.577215664871972
5 137/60 0.5772156649009298
6 49/20 0.5772156649015083
7 363/140 0.5772156649015311
8 761/280 0.5772156649015325
9 7129/2520 0.5772156649015325
10 7381/2520 0.5772156649015325
11 83711/27720 0.5772156649015324
12 86021/27720 0.5772156649015328
13 1145993/360360 0.5772156649015323
14 1171733/360360 0.5772156649015325
15 1195757/360360 0.5772156649015328
16 2436559/720720 0.5772156649015326
17 42142223/12252240 0.5772156649015329
18 14274301/4084080 0.5772156649015325
19 275295799/77597520 0.5772156649015325
20 55835135/15519504 0.5772156649015326
jagy@phobeusjunior:
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.
Here is an answer using limits, but no calculus.
Note that $$ \begin{align} H(2n)-H(n) &=\sum_{k=1}^{2n}\frac1k-\sum_{k=1}^n\frac1k\\ &=\sum_{k=1}^n\frac1{2k-1}+\frac1{2k}-\frac1k\\ &=\sum_{k=1}^n\frac1{2k-1}-\frac1{2k}\\ &=\sum_{k=1}^{2n}(-1)^{k-1}\frac1k\tag{1} \end{align} $$ By the Alternating Series Test, $\displaystyle\sum_{k=1}^\infty(-1)^{k-1}\frac1k$ converges. Call the limit $\alpha$. Futhermore, the Alternating Series Test says that $$ \alpha-\frac1{2n+1}\le H(2n)-H(n)\le\alpha\tag{2} $$
Thus, summing $(2)$ yields $$ (n-m)\alpha-\frac1{2^m}\le H(2^n)-H(2^m)\le(n-m)\alpha\tag{3} $$ $(3)$ says precisely that $$ H(2^n)\sim n\alpha\tag{4} $$
Computation of $\alpha$
In this answer, It is shown that $\left(1+\frac1n\right)^n$ increases and $\left(1+\frac1n\right)^{n+1}$ decreases to $e$. Thus, $$ \left(1+\frac1n\right)^n\le\left(1+\frac1{n+1}\right)^{n+1}\le\dots\le\left(1+\frac1{n+k}\right)^{n+k}\tag{5} $$ and $$ \left(1+\frac1n\right)^{n+1}\ge\left(1+\frac1{n+1}\right)^{n+2}\ge\dots\ge\left(1+\frac1{n+k}\right)^{n+k+1}\tag{6} $$ Putting $(5)$ and $(6)$ together yields, for $0\le k\le n$, $$ \left(1+\frac1{n+k}\right)^{\frac{n}{n+1}}\le\left(1+\frac1{n+k}\right)^{\frac{n}{n+k}\frac{n+k+1}{n+1}}\le\left(1+\frac1n\right)^\frac{n}{n+k}\le\left(1+\frac1{n+k}\right)\tag{7} $$ Therefore, $$ \begin{align} e^\alpha &=\lim_{n\to\infty}\left(1+\frac1n\right)^{n\left(\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\right)}\tag{8} \end{align} $$ and by $(7)$ $$ \begin{align} \left(1+\frac1n\right)^{n\left(\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\right)} &\le\left(1+\frac1{n+1}\right)\left(1+\frac1{n+2}\right)\dots\left(1+\frac1{2n}\right)\\ &=\frac{2n+1}{n+1}\tag{9} \end{align} $$ Using the other direction of $(7)$, we get $$ \left(\frac{2n+1}{n+1}\right)^\frac{n}{n+1} \le\left(1+\frac1n\right)^{n\left(\frac1{n+1}+\frac1{n+2}+\dots+\frac1{2n}\right)}\tag{10} $$ By the Squeeze Theorem, $(8)$, $(9)$, and $(10)$ say $$ e^\alpha=2\tag{11} $$ which, by definition, means $$ \alpha=\log(2)\tag{12} $$ Since $H$ is monotonic, $(4)$, and $(12)$ say that $$ H(n)=\Theta(\log(n))\tag{13} $$