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

Question

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

1. Base Case: $1+\frac{1}{2} \leq 1+\frac{1}{2} = H_1$
2. Inductive Hypothesis: $1 + \frac{k}{2} \leq H_{2^k}$ for all $k \in \mathbb{N}$
3. 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?

Answer 1

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 $$

Answer 2

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.