Prove By Induction $1 + 1/2 + 1/3 + ... + 1/(2^n) ≥ 1 + n/2$

Question

$1 + 1/2 + 1/3 + ... + 1/(2^n) ≥ 1 + n/2$

I'm trying to prove by induction. But i can't really figure out the basis step. if $n = 1$ what would the inequality simplify into? $1 ≥ 1 + 1/2$? I can't really figure out the pattern here.

Answer 1

Base Case: Let $n=1$. Then we have $1+1/2\geq 1+1/2$ and we are done.

Inductive Step: Assume the result holds for $n=k$. We wish to prove it for $n=k+1$. We know that $1+1/2+\cdots+1/2^k\geq 1+k/2$. Therefore we know that $$\sum_{n=1}^{2^{k+1}}\frac{1}{n}\geq 1+k/2+\sum_{n=2^k+1}^{2^{k+1}}\frac{1}{n}$$

Therefore to conclude we just need to show that the last summation is greater than $1/2$. A sum is always greater than it's smallest value times the number of terms, which in this case is $\frac{2^{k+1}-2^k}{2^{k+1}}=\frac{1}{2}$ so we are done.

Notice that as mentioned in the comments, the same idea evoked at the end here can give a proof without the need for induction.

---

There should be another way to do it involving average values. Divide both sides by $2^{-n}$ and what you have on the LHS is the average value of $1/k$ on the set $\{1,2,\ldots,2^n\}$. The RHS is then $2^{-n}+n2^{-(n+1)}$ but I can't seem to see why that is less than the average value in question.