Prove $1 + \frac{n}{2} \leq 1+ \frac{1}{2} +\frac{1}{3} +\cdots + \frac{1}{2^n}$ for all natural numbers $n$ Definitions


*

*$H_n = 1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}$ for all $n \in \mathbb{N}$ 


The Question


*

*Prove $1 + \frac{n}{2} \leq H_{2^n}$ for all $n \in \mathbb{N}$


My Work


*

*
Base Case:

$1+\frac{1}{2} \leq 1+\frac{1}{2} = H_1$


*
Inductive Hypothesis: $1 + \frac{k}{2} \leq H_{2^k}$ for all $k \in \mathbb{N}$


*
Induction Step: $1+\frac{k+1}{2} = 1+\frac{k}{2} + \frac{1}{2} \leq H_{2^k}+\frac{1}{2} \leq H_{2^k} + \frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^{k+1}} = H_{2^{k+1}} $



My Problem


*

*My problem is actually understanding the $H_{2^k}+\frac{1}{2} \leq H_{2^k} + \frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^{k+1}}$ step. I think that's how the proof should finish, but I don't know why.


My Question


*

*Can someone explain why the inequality under the "My Problem" header is true? Or if it even is true, am I going about this proof the wrong way?


you only require:
$$
\frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^{k+1}} = \frac{1}{2^k+1} + \frac{1}{2^k+2} + \cdots + \frac{1}{2^k+2^k} \\ =\sum_{j=1}^{2^k} \frac1{2^k+j} \\ \ge \sum_{j=1}^{2^k} \frac1{2^{k+1}} \\ = \frac12
$$
