So I'm trying to figure out a homework problem. We have to prove it using weak induction.
$$\sum_{j=1}^{2^n}\frac{1}{j}\ge1+\frac{n}{2}$$
The base case is easy, and I have my induction hypothesis as the sum from $j=1$ to $m$ of $\frac{1}{j}$ is greater than or equal to $1 + \frac{m}{2}$. But I can't figure out how to get to the $n+1$ step. Help?
Suppose that the claim holds for some integer $n$. Then note that $$ \sum_{j=1}^{2^{n+1}}\frac{1}{j}=\sum_{j=1}^{2^n}\frac{1}{j}+\sum_{j=2^n+1}^{2^{n+1}}\frac{1}{j}\ge 1+\frac{n}{2}+\frac{2^n}{2^{n+1}}=1+\frac{n+1}{2} $$ where we used the induction hypothesis to get the inequality and used $$ \sum_{j=2^n+1}^{2^{n+1}}\frac{1}{j}\geq \frac{2^n}{2^{n+1}} $$ since we are summing $2^n$ terms each of which is at least $1/2^{n+1}$.