Use induction to prove that $\sum_{k=1}^{2^{n}}\frac{1}{k} \geq 1 +\frac{n}{2}$?

Question

For the base case I have $n = 1$, so ${1\over1} + {1\over2} = {3\over2}, 1 + {1\over2} = {3\over2}$. Hence this is true. For the induction hypothesis we can assume n=k is true also. For the induction step I plug in $n=k+1$ but i'm not sure what to do with it.

Answer 1

For $n=k+1$,

$\large{1+{1\over2}+...+{1\over2^{k+1}}}\geq \large{1+{1\over2}+...+{1\over2^{k}}+{2^k\over2^{k+1}}\geq 1+{n\over2}+{1\over2}=1+{n+1\over2}}$

Answer 2

If $n=1$, then $$ \sum_{k=1}^{2^{n}}\frac{1}{k} = 1 + \frac{1}{2} = 1 + \frac{n}{2}; $$ if $n \geq 1$ is an integer such that $$ \sum_{k=1}^{2^{n}}\frac{1}{k} \geq 1 + \frac{n}{2}, $$ then \begin{align*} \sum_{k=1}^{2^{n+1}}\frac{1}{k} &= \sum_{k=1}^{2^{n}}\frac{1}{k} + \sum_{k=2^{n}+1}^{2^{n+1}}\frac{1}{k}\\ &\geq 1 + \frac{n}{2} + \sum_{k=2^{n}+1}^{2^{n+1}}\frac{1}{k}\\ &= 1 + \frac{n}{2} + \frac{1}{2^{n}+1} + \cdots + \frac{1}{2^{n+1}}\\ &\geq 1 + \frac{n}{2} + \frac{(2^{n+1} - 2^{n})}{2^{n}+1}\\ &= 1 + \frac{n}{2} + \frac{2^{n}}{2^{n}+1}\\ &\geq 1 + \frac{n}{2} + \frac{2^{n}}{2\cdot 2^{n}}\\ &= 1 + \frac{n}{2} + \frac{1}{2}\\ &= 1 + \frac{n+1}{2}. \end{align*}