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?
Best Answer
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}}$$