Proof by induction of summation inequality: $1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots+\frac1{2^n}\ge 1+\frac{n}2$

Prove by induction the summation of $\frac1{2^n}$ is greater than or equal to $1+\frac{n}2$.

We start with $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots+\frac1{2^n}\ge 1+\frac{n}2$$ for all positive integers.

I have resolved that the following attempt to prove this inequality is false, but I will leave it here to show you my progress. In my proof, I need to define P(n), work out the base case for n=1, and then follow through with the induction step. Strong mathematical induction may be used.

This is equivalent to $$\sum_{k=0}^n\frac1{2^k}\ge 1+\frac{n}2\;.$$

Let $P(n)$ be summation shown above.

Base case for $n=1$, the first positive integer,

$$\sum_{k=0}^1\frac1{2^k}=\frac1{2^0}+\frac1{2^1}=1+\frac12=\frac32\ge 1+\frac12=\frac32\;,$$

so base case is true.

Induction step: Assume $P(n)$ is true and implies $P(n+1)$. Thus

$$\sum_{k=0}^{n+1}\frac1{2^k}\ge\frac1{2^{n+1}}+\sum_{k=0}^n\frac1{2^k}\ge 1+\frac{n+1}2\;.$$

This can be written as

$$\sum_{k=0}^{n+1}\frac1{2^k}\ge \frac1{2^{n+1}}+1+\frac{n}2\ge 1+\frac{n+1}2\;.$$

I work the math out but I get stuck contradicting my statement. Please show your steps hereafter so I can correct my mistakes.

Solution 1:

I think that your notation is rather badly confused: I strongly suspect that you’re supposed to be showing that $$\sum_{k=1}^{2^n}\frac1k\ge 1+\frac{n}2\;,\tag{1}$$ from which one can conclude that the harmonic series diverges. The basis step for your induction should then be to check that $(1)$ is true for $n=0$, which it is: $$\sum_{k=1}^{2^n}\frac1k=\frac11\ge 1+\frac02\;.$$

Now your induction hypothesis, $P(n)$, should be equation $(1)$, and you want to show that this implies $P(n+1)$, which is the inequality $$\sum_{k=1}^{2^{n+1}}\frac1k\ge 1+\frac{n+1}2\tag{2}\;.$$ You had the right idea when you broke up the bigger sum into the old part and the new part, but the details are way off:

$$\begin{align*}\sum_{k=1}^{2^{n+1}}\frac1k&=\sum_{k=1}^{2^n}\frac1k+\sum_{k=2^n+1}^{2^{n+1}}\frac1k\\ &\ge 1+\frac{n}2+\sum_{k=2^n+1}^{2^{n+1}}\frac1k\tag{3} \end{align*}$$

by the induction hypothesis $P(n)$. Now look at that last summation in $(3)$: it has $2^{n+1}-2^n=2^n$ terms, and the smallest of those terms is $\dfrac1{2^{n+1}}$, so $$\sum_{k=2^n+1}^{2^{n+1}}\frac1k\ge 2^n\cdot\frac1{2^{n+1}}=\frac12\;.$$ If you plug this into $(3)$, you find that $$\sum_{k=1}^{2^{n+1}}\frac1k\ge 1+\frac{n}2+\frac12=1+\frac{n+1}2\;,$$ which is exactly $P(n+1)$, the statement that you were trying to prove.

You’ve now checked the basis step and carried out the induction step, so you can conclude that $(1)$ is true for all $n\ge 0$.