# Help with Strong Induction

I am stuck on the inductive step of a proof by strong induction, in which I am proving proposition $S(x)$: $$\sum_{i=1}^{2^x} \frac{1}{i} \geq 1 + \frac{x}{2}$$ for $x \geq 0$. I have already finished verifying the base case, $S(0)$, and writing my inductive hypothesis, $S(x)$ for $0 \leq x \leq x + 1$. What I need to prove is $S(x+1)$: $$\sum_{i=1}^{2^{x+1}} \frac{1}{i} \geq 1 + \frac{x+1}{2}$$ but I cannot figure out how to go from point A to point B on this.

What I have so far is the following (use of inductive hypothesis denoted by I.H.): \begin{eqnarray*} \sum_{i=1}^{2^{x+1}} \frac{1}{i} & = & \sum_{i=1}^{2^x} \frac{1}{i} + \sum_{i=2^x+1}^{2^{x+1}} \frac{1}{i} \\ & \stackrel{I.H.}{\geq} & 1 + \frac{x}{2} + \sum_{i=2^x+1}^{2^{x+1}} \frac{1}{i} \\ \end{eqnarray*} But in order to complete the proof with this approach, I need to show that $$\sum_{i=2^x+1}^{2^{x+1}} \frac{1}{i} \geq \frac{1}{2}$$ and I have absolutely no idea how to do that. When I consulted with my professor, he suggested that I should leverage the inequality more than I am, but I frankly can't see how to do that either. I have been staring at this proof for over 6 hours, will someone please give me a hint? Or, more preferably, could you explain a simpler/easier way to go about this proof? Thank you.

• Notice that in your last sum, $i$ is always greater than $2^x$. That can give you an upper bound on all of the $1/i$ terms – JonathanZ Sep 5 '17 at 4:11

Note that $\frac{1}{i}\geq \frac{1}{2^{x+1}}, \forall i\in \{2^x+1,2^x+2,....,2^{x+1}\}$ $$\Rightarrow \sum_{i=2^x+1}^{2^{x+1}} \frac{1}{i} \geq 2^x\cdot \frac{1}{2^{x+1}}=\frac{1}{2}$$