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

marked as duplicate by Did, uniquesolution, Arnaldo, Namaste discrete-mathematics Mar 30 '17 at 14:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


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

  • $\begingroup$ Can you explain the $\sum_{j=1}^{2^k} \frac1{2^{k+1}} \\ = \frac12$ step? $\endgroup$ – Dunka Mar 30 '17 at 9:48

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.