Use mathematical induction to show that $H_{2^n} \geq 1+ \frac{n}{2}$

An Inequality for Harmonic Numbers. The harmonic numbers $H_j, j=1,2,3,...,$ are defined by $$H_j = 1 + \cfrac{1}{2}+\cfrac{1}{3}+...+\cfrac{1}{j}$$

Use mathematical induction to show that $$H_{2^n} \geq 1+ \frac{n}{2}$$ whenever $n$ is a nonnegative integer.

BASIS STEP: $P(0)$ is true, because $H_{2^0}=H_1=1 \geq 1+\dfrac{0}{2}$

INDUCTIVE STEP: The inductive hypothesis is the statement that $P(k)$ is true, that is, $H_{2^k} \geq 1 +\dfrac{k}{2}$, where $k$ is an arbitrary nonnegative integer. We must show that if $P(k)$ is true, then $P(k+1)$, which states that $H_{2^{k+1}} \geq 1 +\dfrac{k+1}{2}$, is also true. So, assuming the inductive hypothesis, it follows that $$H_{2^{k+1}} = 1+ \frac{1}{2} + \frac{1}{3} + ...+ \frac{1}{2^k} + \frac{1}{2^k+1}+...+ \frac{1}{2^{k+1}}$$ $$=H_{2^k}+\frac{1}{2^k+1}+...+ \frac{1}{2^{k+1}}$$ $$\geq (1+\frac{k}{2})+ \frac{1}{2^k+1}+...+ \frac{1}{2^{k+1}} \qquad ...(?)$$ $$\geq (1+\frac{k}{2})+2^k \cdot \frac{1}{2^{k+1}}\qquad ...(??)$$ $$\geq (1+\frac{k}{2}) + \frac{1}{2}$$ $$=1+\frac{k+1}{2}$$ I don't understand what is going on at lines $(?)$ and $(??)$, why did it change from $=H_{2^k}$ to $\geq (1+\dfrac{k}{2})$ can somebody explain it to me?

• What is $H_{2^n}$? – R_D Oct 30 '15 at 13:24
• @Rise I updated the question. – Gjekaks Oct 30 '15 at 13:27

The first inequality is the inductive hypothesis.

As for the second, note that for all $j \in \{ 1, \dots 2^k\}$, $$\frac{1}{2^k+j} \ge \frac{1}{2^{k+1}}$$ So that $$\sum_{j=1}^{2^k} \frac{1}{2^k+j} \ge \sum_{j=1}^{2^k} \frac{1}{2^{k+1}} = 2^k \frac{1}{2^{k+1}}$$

• Actually this is one of the standard proofs of the fact that the harmonic series is divergent. – Crostul Oct 30 '15 at 13:32

(base case, etc. omitted)

assume $H_{2^n}\ge 1+{n\over 2}$

$H_{2^n}+{1\over 2}\ge 1+{n\over 2}+{1\over 2}$

${1\over 2}={{2^n}\over{2^n+2^n}}={1\over {2^n+2^n}}_{(1)}+{1\over {2^n+2^n}}_{(2)}+...+{1\over {2^n+2^n}}_{(2^n)}$

$H_{2^{n+1}}=H_{2^n}+{1\over {2^n+1}}_{(1)}+{1\over {2^n+2}}_{(2)}+...+{1\over {2^n+2^n}}_{(2^n)}\ge H_{2^n}+{1\over {2^n+2^n}}_{(1)}+{1\over {2^n+2^n}}_{(2)}+...+{1\over {2^n+2^n}}_{(2^n)}=H_{2^n}+{1\over 2}\ge 1+{n\over 2}+{1\over 2}=1+{{n+1}\over 2}$

I think you first have to understand the abstract concept of the proof by induction. In fact, you show that some conjectured result that depends on a natural number n holds for an initial step, say n=1. The second step is to show that if it holds for n=k, then it also holds for n=k+1. Proving these two things, you can follow that it holds for any natural number n. This is based on the axiom that k is followed by k+1 for any natural number. Starting with n=1 (or n=0), you can now iteratively go to any number you want. See also Wikipedia.

So in the present application, you showed in the first (basis) step, that the assumption holds for n=0. What is left to do is the induction step, namely to show that under the assumption that our identity holds for n=k, it also has to hold for n=k+1. Of course you have to use your assumption, to proof something out of it.

Therefore you manipulate the term so that you can directly insert the assumption, as it happens in line (?). The other terms don't bother the inequality, since they are all non-negative (in fact, strictly positive).

Now in line (??) you have to do some work (which was already described well by Crostul and is just a repetition in other words). Each single term of $$\frac1{2^k+1},\frac1{2^k+2},\dots,\frac1{2^{k+1}}$$ is smaller than $$\frac{1}{2^k}.$$ Second, the number of terms is $2^k$, since $$2^{k+1}-2^k=2^k2-2^k=2^k(2-1)=2^k.$$ It directly follows that $$\frac1{2^k+1}+\frac1{2^k+2}+\dots+\frac1{2^{k+1}}<2^k\frac1{2^k}.$$