Prove by induction $1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{3} + \ldots + \frac{1}{2^n} \ge 1 + \frac {n}{2}$ 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? 
 A: 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.
A: 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)$$
