I'm stuck on an excercise in my maths class. How can I find an explicit lower bound for the harmonic series sum:



closed as off-topic by FrankW, David Richerby, D.W., Yuval Filmus, Gilles Oct 13 '14 at 17:43

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – FrankW, David Richerby, D.W., Yuval Filmus, Gilles
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ Why don't you ask on Mathematics? $\endgroup$ – FrankW Oct 13 '14 at 14:09
  • $\begingroup$ $0$ is an obvious one. How good does this bound have to be? What do you know about the harmonic series? You should ask on Mathematics (not here, the question is off-topic) with a bit more information about what you already know and what you're looking for. $\endgroup$ – Gilles Oct 13 '14 at 17:42

You should have asked this on Math Stack Exchange

But here's the soultion $$\sum_{x=1}^{2^k}\frac{1}{x}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}+\frac{1}{9}+ \cdots+\frac{1}{2^k}$$ can be written as $$\sum_{x=1}^{2^k}\frac{1}{x}=1+\left(\frac{1}{2}\right)+\left(\frac{1}{3}+\frac{1}{4}\right)+\left(\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}\right)+ \cdots+\frac{1}{2^k}$$ It can be observed that $$\frac{1}{3}+\frac{1}{4}=\frac{7}{12}>\frac{1}{2}$$ $$\frac{1}{5}+\frac{1}{6}+\frac{1}{7}+\frac{1}{8}=\frac{533}{840}>\frac{1}{2}$$ similarly $$\frac{1}{2^m+1}+\frac{1}{2^m+2}+\cdots+\frac{1}{2^m+2^m}>\frac{1}{2}$$ so, $$\sum_{x=1}^{2^k}\frac{1}{x}\ge1+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+\frac{1}{2}+ \cdots+\frac{1}{2}$$ $$\sum_{x=1}^{2^k}\frac{1}{x}\ge1+\frac{k}{2}$$


You can get a very good bound by using an integral. Since $1/x$ is decreasing, we have $$ \int_t^{t+1} \frac{dx}{x} \leq \int_t^{t+1} \frac{dx}{t} = \frac{1}{t}. $$ Therefore $$ \sum_{t=1}^n \frac{1}{t} \geq \int_1^{n+1} \frac{dx}{x} = \log (n+1). $$ Similarly, $$ \sum_{t=1}^n \frac{1}{t} \leq 1 + \int_1^n \frac{dx}{x} = \log n + 1. $$ Even better estimates show that $$ \sum_{t=1}^n \frac{1}{t} = \log n + \gamma + O\left(\frac{1}{n}\right), $$ and the Wikipedia article on Euler's constant $\gamma$ contains even more accurate expansions.


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