# Inequality of finite harmonic series

I'm asked to prove that for $n\in \mathbb{N}$ $$\frac{1}{1} + \frac{1}{2} +\cdots+\frac{1}{n} \geq 1 + \frac{n}{2}$$ by induction.

I've got a feeling that the problem isn't right (since it isn't true for any $n\in \mathbb{N}$), does anyone know the result and what it should be?

Edit: The author says that the result can be used to prove that the harmonic series diverges.

-
It should be $\leq$. –  Billy Sep 15 '12 at 6:34
Here are some collections of proofs of divergence of harmonic series (the one you refer to is the first one). Steven J. Kifowit and Terra A. Stamps: The Harmonic Series Diverges Again and Again e.g. here; Steven J. Kifowit: More Proofs of Divergence of the Harmonic Series, see e.g. here. I think I have seen some question with several proof of this fact at this site, but I cannot find it now. –  Martin Sleziak Sep 15 '12 at 8:16

Given that the result is supposed to be usable in proving the divergence of the harmonic series, it was probably supposed to be

$$\sum_{k=1}^{2^n}\frac1k=1+\frac12+\ldots+\frac1{2^n}\ge 1+\frac{n}2\;.$$

This can indeed be proved fairly easily by induction on $n$ and can be used to prove the divergence of the harmonic series.

(My earlier answer $-$ that the inequality is the wrong way round $-$ is correct in the sense that the reversed inequality is true, but it’s clearly not what the author had in mind.)

-
Thank you for your reply. I forgot to mention my edit - does that change anything (I'm no hero at series). –  Henrik Sep 15 '12 at 6:48
@Henrik: Yes, it does. Hang on a minute, and I’ll change my answer to match. –  Brian M. Scott Sep 15 '12 at 6:51
@Henrik: Billy and Brian are right. Consider $n = 3$. On the left hand side, you have $1 + \frac{1}{2} + \frac{1}{3} = \frac{11}{6}$, and on the right hand side you have $1 + \frac{3}{2} = \frac{5}{2}$. As $\frac{11}{6} < \frac{5}{2}$, the inequality in the question is the wrong way around. –  Michael Albanese Sep 15 '12 at 6:52
Ah. No, given your edit, I don't think my comment is what the author intended - it's true, but unhelpful. –  Billy Sep 15 '12 at 6:56
@BrianM.Scott: I think it's worth being clear: the left hand side of your inequality is $1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{2^n - 1} + \frac{1}{2^n}$, not (as I first read it) $1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^n}$. –  Billy Sep 15 '12 at 6:57

It has been suggested that the inequality be reversed. Certainly we get a correct inequality, unfortunately a fairly uninteresting one. We propose that instead we let $$f(n)=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{2^n},$$ and show that $f(n)\ge 1+\dfrac{n}{2}$ for every integer $n \ge 0$.

It is clear that the result holds when $n=0$. Suppose that the inequality holds at $n=k$. We show that it holds at $n=k+1$. We have $$f(k+1)=f(k)+\frac{1}{2^k+1}+\frac{1}{2^k+2}+\cdots +\frac{1}{2^{k+1}}.\tag{1}$$ Each of $\frac{1}{2^k+1}$, $\frac{1}{2^k+2}$, and so on up to $\frac{1}{2^{k+1}}$ is $\ge \frac{1}{2^{k+1}}$, and there are $2^k$ such terms. So their sum is $\ge \frac{1}{2}$. Thus $$f(k+1)\ge f(k)+\frac{1}{2}\ge 1+\frac{k}{2}+\frac{1}{2}=1+\frac{k+1}{2},$$ and now we have done the induction step.

Remark: This is a somewhat formalized version of the usual argument that the harmonic series diverges.

-

Hint: In the following sum, there are $2^{k-1}$ terms, each at least as big as $2^{-k}$; therefore, $$\sum_{j=2^{k-1}+1}^{2^k}\frac1j\ge2^{k-1}2^{-k}=\frac12$$ Furthermore, we also have that \begin{align} \sum_{j=1}^{2^n}\frac1j &=1+\sum_{k=1}^n\sum_{j=2^{k-1}+1}^{2^k}\frac1j \end{align}

-