16
$\begingroup$

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.

$\endgroup$
  • 9
    $\begingroup$ If you alrady have Riemann integration at your disposal, then $\sum_{k=1}^n\frac1 k\approx \int_1^{n+1}\frac{\mathrm d x}{x}$. $\endgroup$ – Hagen von Eitzen Feb 17 '13 at 18:05
  • $\begingroup$ @HagenvonEitzen Is that the same as the Riemann sum? Making constant width blocks above/below the curve to show upper/lower bounds? I guess in a monotonic curve, limiting the width to $0$ should give the approximate integral. Is that right? $\endgroup$ – mayank Feb 17 '13 at 18:08
  • 3
    $\begingroup$ It's an upper Riemann sum. As $\ln$ is monotonic, i.e. $\frac1k\ge \frac1x\ge \frac1{k+1}$ for $x\in[k,k+1]$, $\sum_{k=1}^n\frac1k\ge \int_1^{n+1}\frac{\mathrm dx}x\ge \sum_{k=2}^{n+1}\frac1k$. $\endgroup$ – Hagen von Eitzen Feb 18 '13 at 17:47
16
$\begingroup$

$$ 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.

$\endgroup$
16
$\begingroup$

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} $$

$\endgroup$
  • $\begingroup$ Took me some time to understand, but very nice! Thank you very much! $\endgroup$ – mayank Feb 18 '13 at 17:30
  • $\begingroup$ @mayank: I interpreted "simple" as meaning "fewer prerequisites". Answers using calculus will be shorter, but whether they are simpler is a matter of one's point of view. I was excited by the non-calculus proof that $H(2n)-H(n)=\log(2)$. I have never seen this approach before. $\endgroup$ – robjohn Feb 18 '13 at 17:39
  • $\begingroup$ Yes, it was very nice. And as an added bonus, I came across the other question that you linked to in this answer, and another question where you linked this answer. $\endgroup$ – mayank Feb 18 '13 at 17:49
  • $\begingroup$ Rob. Happy New Year! This answer is excellent - I love it! One thing that I have come to appreciate more these days is a presentation that relies on a "back to the basics" approach. Well done here! +1 - Mark $\endgroup$ – Mark Viola Jan 16 '16 at 1:48
  • $\begingroup$ Rob, I was reviewing the post and wondering how the sum of $(2)$ yields $(1)$. I assume that by summing, you meant $$\alpha (n-m)-\sum_{\ell =m+1}^n \frac{1}{2\ell +1} \le \sum_{\ell =m+1}^{n}\left(H(2\ell)-H(\ell)\right)\le \alpha (n-m)$$How does the middle sum equal $H(2^n)-H(2^m)$? and how does the left-hand side sum yield the term $1/2^m$? $\endgroup$ – Mark Viola Nov 17 '16 at 0:01
6
$\begingroup$

Here's my favorite "calculus-free" proof that $H_n = \Theta(\log n)$. This proof is essentially an extension of the calculus-free proof that the harmonic series diverges.

Start with the powers of 2, $n = 2^k$, and break up $H_{2^k}$ into $k$ groups, each one twice as large as the previous: $$\begin{align*} H_{2^k} = &\sum_{j = 1}^{2^k} \frac{1}{j} \\ = & 1 + \\ &\frac{1}{2} + \frac{1}{3} + \\ &\frac{1}{4}+\frac{1}{5} + \frac{1}{6} + \frac{1}{7}\\ & \cdots\\ & \frac{1}{2^{k-1}} + \frac{1}{2^{k-1} + 1} + \cdots + \frac{1}{2^k - 1} \end{align*}$$ There's also one extra term, $\frac{1}{2^k}$.

We can bound each group above and below by a constant by bounding each term by the power of 2 above and below it. \begin{array}{lll} \frac{1}{2}& \leq 1 &\leq 1\\ \frac{1}{4}+\frac{1}{4}& \leq \frac{1}{2} + \frac{1}{3} &\leq \frac{1}{2} + \frac{1}{2}\\ \frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}& \leq \frac{1}{4}+\frac{1}{5} + \frac{1}{6} + \frac{1}{7} & \leq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}\\ & \cdots &\\ \frac{1}{2^k} + \frac{1}{2^k} + \cdots + \frac{1}{2^k} & \leq \frac{1}{2^{k-1}} + \frac{1}{2^{k-1} + 1} + \cdots + \frac{1}{2^k - 1} & \leq \frac{1}{2^{k-1}} + \frac{1}{2^{k-1}} + \cdots + \frac{1}{2^{k-1}} \end{array} Each of the left-hand sums is $\frac{1}{2}$. Each of the right-hand sums is 1. Together we have $\frac{1}{2}k +\frac{1}{2^k}\leq H_{2^k} \leq k + \frac{1}{2^k}$. Written in terms of $n$, $$ \frac{1}{2} \log_2 n \leq H_n \leq \log_2n + 1$$

This is essentially the whole proof: it says when $n = 2^k$, $H_n = \Theta( \log n)$. For $n$ that aren't powers of 2, letting $n_-$ and $n_+$ be the surrounding powers of 2 of $n$, by monotonicity of $H_n$ and the observation that $$n/2 < n_- < n < n_+ < 2n$$ we have $$\frac{1}{2}\log_2(n/2) < \frac{1}{2}\log_2 n_- < H_{n_-} < H_n < H_{n_+} < \log_2 n_+ +1< \log_2 (2n)+1$$ $$\frac{1}{2} \log_2n - \frac{1}{2} < H_n < \log_2 n + 2$$ And so $H_n = \Theta(\log n)$.

$\endgroup$
5
$\begingroup$

Just consider that $\frac{1}{x + 1} < \frac{1}{x}$, plot both and see that $H_n$ is the area under a "staircase" sandwiched between both curves (the image shows the lower bound for a similar situation). This gives rather tight bounds on $H_n$. Lower bound and "staircase"

$\endgroup$
  • 1
    $\begingroup$ Yes, I think this is the Riemann sum - upper and lower sums should give the Riemann integral - as hinted in the comments to the question. Thank you very much, and +1 for the beautiful and easy to understand graph (and explanation). $\endgroup$ – mayank Feb 18 '13 at 17:33
  • 2
    $\begingroup$ Just notice that there are "triangles" between the curve and the staircase, and you end up approximating $H_n$ as halfway between upper/lower, and get a (not so) crude estimate of 0.5 for $\gamma$... $\endgroup$ – vonbrand Feb 18 '13 at 17:37
4
$\begingroup$

Let $u_n=H_n-\log n$. If we prove that the sequence $(u_n)_n$ is convergent (it's limit is the Euler constant $\gamma$) then we conclude that $H_n=\Theta(\log n)$.

Moreover, We know that the sequence $(u_n)$ is convergent iff the serie $\sum( u_{n}-u_{n-1})$ is convergent so we calculate $$u_{n}-u_{n-1}=\frac{1}{n}+\log(1-\frac{1}{n})=-\frac{1}{2n^2}+o(\frac{1}{n^2}),$$ and we show easily its convergence (Riemann series).

$\endgroup$
1
$\begingroup$

Apply the Abel partial summation formula

$\sum_{k \le x} a_k \varphi(k) = A(x)\varphi(x) - \int_1^x A(u)\varphi'(u) du$

where $A(x) = \sum_{k \le x} a_k$.

We have $\sum_{k \le x} 1.\frac1{k} = [x].\frac1{x} +\int_1^x[u]\frac1{u^2} du$

with $A(x) = \sum_{k \le x}1=[x]$ and $\varphi(u)=\frac1{u}$.

($\{{u}\}$ denote fractional part of u, and $[u]$ the entire part.)

As $u=[u]+\{u\}$, we have $\sum_{k \le x}\frac1k= \frac{[x]}{x}+ \int_1^x \frac1{u}du-\int_1^x \frac{\{u\}}{u^2}du = O(1) + \ln (x) - O(1/x).$

Hence $\sum_{k \le x} \frac1k=\ln(x) + O(1).$

Another method is to apply the Euler-MacLaurin formula

$\sum_{i=p}^{q}f\left( i\right) =\int_p^q f(x)~{\rm d}x+\frac{f\left( p\right) +f\left( q\right) }{2} +\sum_{j=1}^k\frac{b_{2j}}{(2j)!}\left(f^{(2j-1)}(q)-f^{(2j-1)}(p)\right)+R_k.$

The formula give with $f(u)=\frac1u$ immediately $\sum_{k \le x} \frac1k=\ln(x) + O(1).$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.