Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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

3 Answers 3

up vote 10 down vote accepted

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

share|improve this answer
    
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

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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