2(n+1−1)<1+21+…+n1<2n
Base Case: n=1
2(2−1)<1<2
2−1<21<1
2≈1.414<1.5<2
Assume: 2(k+1−1)<1+21+…+k1<2k
Prove: 2(k+2−1)<1+21+…+k+11<2k+1
1) 1+21+…+k1+k+11<2k+k+11=k+12k(k+1)+1
Using inequality xy≤2x+y , we get k+12k(k+1)+1≤k+1(2k+1)+1=2k+1
Therefore, 1+21+…+k+11<2k+1
2) 1+21+…+k1+k+11>2(k+1−1)+k+11=k+12(k+1)+1−2=k+12k+3−2
Using inequality xy≤2x+y , we get (k+1)(k+2)≤22k+3 .
So, 2k+2≤k+12k+3 .
Therefore, 1+21+…+k+11>2k+2−2=2(k+2−1)