Show that $H_{2^n}$ $\leq$ $1+n$ with induction

Question

Use mathematical induction to show that $H_{2^n}$ $\leq$ $1+n$, whenever n is a nonnegative integer.
PS: $H_{2^n}$ denotes the $2^n$th harmonic number.

Answer 1

Since the induction basis and the hypothesis of induction are easy steps you can do them. Now, if it is supposed that $H_{2^k}\le 1+k$ for some integer $k\ge 1$ we have \begin{align*} H_{2^{k+1}}&=H_{2^k}+\sum_{j=1}^{2^k}\frac{1}{2^k+j}\\[5pt] &\le 1+k+\sum_{j=1}^{2^k}\frac{1}{2^k}\\[5pt] &= 1+(k+1) \end{align*}