0
$\begingroup$

Picture of my problem

The problem i am trying to solve is in the link above. I am a little stuck on what to do after the inductive hypothesis of the problem. I first solved the base case where n = 0. Then i assumed P(k) is true where p is the expression in the problem. I then did the inductive hypothesis to get $$ k + 1 + .... + 1/ 2^{k+1} \leq ((k+1) + 1) $$ After that i do not know what step to get to finish the proof.

$\endgroup$
0
$\begingroup$

Your title does not match the question.

You can write $$1 + \frac 12 + \cdots + \frac 1{2^{n+1}} = \left( 1 + \frac 12 + \cdots + \frac 1{2^{n}}\right) + \left(\frac 1{2^n + 1} + \frac{1}{2^n + 2} + \cdots + \frac{1}{2^n + 2^n}\right).$$

It is simple to see that $$\frac 1{2^n + 1} + \frac{1}{2^n + 2} + \cdots + \frac{1}{2^n + 2^n} \le \underbrace{\frac{1}{2^n} + \frac{1}{2^n} + \cdots + \frac{1}{2^n}}_{2^n \text{times}} = 1,$$ and in light of the induction hypothesis $$1 + \frac 12 + \cdots + \frac 1{2^{n}} \le n+1$$ you get the result at once provided you verified the base case correctly.

$\endgroup$
0
$\begingroup$

Our inductive hypothesis is $$1+ \frac12 + \frac13 + ... + \frac1{2^k} \le k+1 $$

Then $$ 1+ \frac12 + \frac13 + ... + \frac1{2^k} + \frac1{2^k+1} + ... + \frac1{2^{k+1}} \le k+1 + \frac1{2^k+1} + ... + \frac1{2^{k+1}} \\ \le k+1 + \frac1{2^k} + ...+ \frac1{2^k} \\ = k+1 + \frac1{2^k}\times2^k \\ = k+2$$

This is what we wanted. Notice that the number of term $\frac1{2^k}$ is $2^{k+1} - (2^k+1)+1 = 2^k$.

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