1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – JonathanZ Sep 5 '17 at 4:11
0
$\begingroup$

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

$\endgroup$

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.