# Lower bound of this harmonic series sum [closed]

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

$$\sum_{x=1}^{2^m}\frac{1}{x}\,?$$

## closed as off-topic by FrankW, David Richerby, D.W.♦, Yuval Filmus, Gilles 'SO- stop being evil'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 'SO- stop being evil'
If this question can be reworded to fit the rules in the help center, please edit the question.

• Why don't you ask on Mathematics? – FrankW Oct 13 '14 at 14:09
• $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. – Gilles 'SO- stop being evil' 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.