So I'm trying to figure out a homework problem. We have to prove it using weak induction.


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?

  • $\begingroup$ 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. $\endgroup$ – Robert Howard Feb 21 at 21:50
  • $\begingroup$ 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? $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.