# inductive proof for $\sum_{i=0}^{2^n} 1/(i+1) \leq n + 1$

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.

• – Lord Shark the Unknown Oct 31 '18 at 20:15
• Do you know the standard proof that $\sum1/i=\infty$? You only need a minor tweak to that proof to show what you want to show. – Arthur Oct 31 '18 at 20:27

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