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?


If $n\leq 2^k$, then $$\frac{1}{2^k+n}\geq \frac1{2^k+2^k}=\frac1{2^{k+1}}$$ Doing this substitution, we now have a sum of $2^k$ identical fractions, which may then be simplified greatly.
