Prove that $\sum_{k=1}^{2^n} \frac{1}{k}\ge 1+\frac{n}{2}$

Question

I want to prove this statement for $\forall n\in \mathbb{N}\space $by induction:

$$\sum_{k=1}^{2^n} \frac{1}{k}\ge 1+\frac{n}{2}$$

Step 1: $n=1$

$$\implies1+\frac{1}{2}\le1+\frac{1}{2} \checkmark$$

Step 2: Assume the inequality holds for some $m$. Show that it holds for $m+1$

$$\implies \sum_{k=1}^{2^{m+1}} \frac{1}{k} \ge 1+\frac{m+1}{2} \\ \iff \color{blue}{\sum_{k=1}^{2^m}\frac{1}{k}}+\frac{1}{2^{m+1}} \ge \color{blue}{1+\frac{m}{2}}+ \frac{1}{2}$$

I assumed the inequalitie holds for $m$ (the blue part). To show that it holds for $m+1$ I have to show that $$\frac{1}{2^{m+1}} \ge \frac{1}{2}$$ However, this statement is false for all $m>1$. What am I doing wrong?

Answer 1

$$\sum_{k=1}^{2^{m+1}} \frac1k$$ is not equal to

$$\sum_{k=1}^{2^m}\frac{1}{k} + \frac{1}{2^{m+1}}$$

It is, in fact, equal to

$$\sum_{k=1}^{2^m}\frac{1}{k} +\color{red}{ \frac{1}{2^m+1} + \frac{1}{2^m+2} +\cdots}+ \frac{1}{2^{m+1}}.$$

You missed some (actually, almost half of all) summands. To conclude your proof, think about how many summands there are in the above expression (the ones in red and the last one).

Answer 2

Note that$$\sum_{k=1}^{2^{m+1}}\frac1k=\sum_{k=1}^{2^m}\frac1k+\sum_{k=2^m+1}^{2^{m+1}}\frac1k.$$You are assuming that $\displaystyle\sum_{k=1}^{2^m}\frac1k\geqslant1+\frac m2$. Now, use the fact that$$\sum_{k=2^m+1}^{2^{m+1}}\frac1k\geqslant2^m\times\frac1{2^{m+1}}=\frac{2^m}{2^{m+1}}=\frac12.$$

Answer 3

$\sum_{k=1}^{2^n}1/k=$

$1+1/2 + (1/3+1/4)+(1/5+16/+1/7+1/8)+....$

$+( 1/(2^{n-1}+1)+......1/2^n) \ge $

$1+1/2 +2/4 +4/8+.............+(2^n-2^{n-1})/(2^n)=$

$1+ 1/2+1/2...........1/2 =$

($n$ summands $1/2$)

$1+n/2.$