Let $H_n = \sum_{j=1}^n \frac 1j$. I'm trying to prove that $H_{2^n}\ge 1+\frac n2$ using the principle of mathematical induction. The base step was no problem but I'm stuck on the inductive step:
$$H_{2^{k+1}}=\sum_{j=1}^{2^{k+1}}\frac 1j = \sum_{j=1}^{2(2^{k})}\frac 1j = \sum_{j=1}^{2^k}\frac 1j + \frac 1{2^k+1} + \cdots + \frac{1}{2(2^k)} \ge 1 + \frac k2 + \frac{1}{2^k+1} + \cdots + \frac{1}{2(2^k)}$$
And here's where I'm stuck. Clearly I need to show that $\frac{1}{2^k+1} + \cdots + \frac{1}{2(2^k)} =\sum_{j=1}^{2^k}\frac{1}{2^k+j}\ge \frac 12$. I don't see any way to prove this except with another proof by induction that'll clearly lead to a similar problem.