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.

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