3
$\begingroup$

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.

  • 2
    It should be $\leq$.2012-09-15
  • 0
    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](http://prairiestate.edu/skifowit/harmapa.pdf); Steven J. Kifowit: More Proofs of Divergence of the Harmonic Series, see e.g. [here](http://prairiestate.edu/skifowit/harm2.pdf). I think I have seen some question with several proof of this fact at this site, but I cannot find it now.2012-09-15
  • 0
    @miracle173 thanks for the input, have you read the entire question though?2017-08-28

3 Answers 3

10

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

  • 0
    Thank you for your reply. I forgot to mention my edit - does that change anything (I'm no hero at series).2012-09-15
  • 0
    @Henrik: Yes, it does. Hang on a minute, and I’ll change my answer to match.2012-09-15
  • 0
    @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.2012-09-15
  • 0
    Ah. No, given your edit, I don't think my comment *is* what the author intended - it's true, but unhelpful.2012-09-15
  • 0
    @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}$.2012-09-15
  • 0
    @Billy: It wouldn’t have occurred to me to read it that way without more evidence, but I’ve added a summation to make it absolutely clear.2012-09-15
  • 0
    @BrianM.Scott A "me too" to Billy's comment. My eyes went to the expanded version of the sum before they went to the sigma, and I too initially thought it meant $1+\frac 12 +\frac 14+\frac 18 +\cdots+\frac 1{2^n}$2012-09-15
  • 0
    @David: I take the more obvious progression to be the default. Had I intended powers of $2$, I’d have included at least one early term with an exponent.2012-09-15
5

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.

1

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