Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

Question

Prove by induction $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$

I can't explain in words how the left hand side of the equation is achieved soI shall provide an example. When $n = 2$, $\frac{1}{2^2} = \frac{1}{4}$ so the left hand side will be $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}$. When $n = 3$, $\frac{1}{2^3} = \frac{1}{8}$, so the left hand side will be $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8}$ and so forth.

I have gotten up to the point where it is calculating the algebra. However, the result ends up being $ 1 + \frac{[2^(k+1)*k] + 2}{2(2^{k+1}} \le 1+ \frac{k+1}{2}$ when the following should be $\ge$. What can I do to solve the question?

Answer 1

Base case $(n = 1)$:

$$ 1 + \frac{1}{2} = 1 + \frac{n}{2}$$ $$ 1 + \frac{1}{2} = 1 + \frac{1}{2}$$

The inductive step:

$$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^n} \geq 1 + \frac{n}{2}$$

We must show that:

$$1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{2^{n+1}} \geq 1 + \frac{n}{2} + \frac{1}{2}$$

This is equivalent to the statement $$\frac{1}{2^{n}+1} + \cdots + \frac{1}{2^{n+1}} \geq \frac{1}{2}$$

Because $$\frac{1}{2^{n}}\left(\frac{1}{1+2^{-n}} + \cdots + \frac{1}{2}\right) \geq\frac{1}{2^{n}}\left(\underbrace{(2^{n+1}-2^n)}_{\text{number of terms}}\frac{1}{2}\right) \geq \frac{2-1}{2} = \dfrac{1}{2}$$

The statement is true because $\frac{1}{2}$ is a lower bound of the $2^{n+1}-2^n$ terms in the series.

This is just going "backwards" from the proof that the harmonic series is divergent.

Answer 2

Hint: Look at your example, appropriately grouped and then with terms made systematically smaller:

$$1+{1\over2}+\left({1\over3}+{1\over4}\right)+\left({1\over5}+{1\over6}+{1\over7}+{1\over8}\right) \ge1+{1\over2}+\left({1\over4}+{1\over4}\right)+\left({1\over8}+{1\over8}+{1\over8}+{1\over8}\right)$$