# How do I prove the following summation notation problem using weak induction?

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?

• Welcome to MSE! You can find a tutorial on how to format your posts with MathJax here. It's standard to do so here, and the basics of MathJax are pretty easy to pick up. – Robert Howard Feb 21 at 21:50
• I think this is easier if you actually expand the terms of this series, and then group them in terms of what you're adding for each increment of $n$: $\left(\frac11\right) + \left(\frac12\right) + \left(\frac13+\frac14\right)+\left(\frac15+\frac16+\frac17+\frac18\right)+\cdots$. Does that make sense? – Brian Tung Feb 21 at 21:53

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}$$.