Prove Harmonic Series Statement

Question

Show that for all n ≥ 0: H2n ≤ 1 + n

I have already done it for bigger or equal to one to prove that it eventually reaches infinity but how would I do this one?

Answer 1

The inequality holds for $n \ge 1$ ($H_0$ is not defined). Indeed, for $n \ge 1$,

\begin{align} H_{2^n} &= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n}\\ &< 1 + \left(\frac{1}{2} + \frac{1}{2}\right) + \left(\frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4}\right) + \cdots + \Bigl(\underbrace{\frac{1}{2^{n-1}} + \cdots + \frac{1}{2^{n-1}}}_{2^{n-1}\, \text{times}}\Bigr)\\ &= 1 + \underbrace{1 + 1 + \cdots + 1}_{\text{$n-1$ times}}\\ &< 1 + n \end{align}