Need some help starting this proof. I am not sure where to begin. Any guidance would be much appreciated.
$$\sum_{i=1}^{2^n}{1/i} \ge 1 + n/2$$
I know I need to induct on n.
here's what I have so far:
a) $p(1) : 1/1 + 1/2 \ge 1 + 1/2$ which is true.
b) $p(n) \Rightarrow p(n+1) $
$$\sum_{i=1}^{2^{n+1}}{1/i} = \sum_{i=1}^{2^n}{1/i} + \sum_{i={2^n+1}}^{2^{n+1}}{1/i}$$
I know that $\sum_{i=1}^{2^n}{1/i} \ge 1 +n/2$ but am having trouble going from here.
Can anyone provide the complete proof?
On
You're right on track. As you note, $$ \sum_{k=1}^{2^{n+1}}\frac{1}{k} = \sum_{k=1}^{2^n} \frac{1}{k} + \sum_{k=2^n+1}^{2^{n+1}}\frac{1}{k} \geq 1 + \frac{n}{2} + \sum_{k=2^n+1}^{2^{n+1}}\frac{1}{k} $$ So you need to show that $\sum_{k=2^n+1}^{2^{n+1}}\frac{1}{k} \geq \frac{1}{2}$.
Now there are $2^n$ terms in that sum, and each one of them is larger than $\frac{1}{2^{n+1}}$, so ...
$$ \sum_{k=2^n+1}^{2^{n+1}}\frac{1}{k} \geq \sum_{k=2^n+1}^{2^{n+1}}\frac{1}{2^{n+1}} = \frac{2^n}{2^{n+1}} = \frac{1}{2} $$
Follow the same as the usual proof that the entire harmonic series diverges, but stop with the finite part you want:
\begin{align}\sum_{i=1}^{2^n} \frac1{i}&=1+\left(\frac12\right)+\left(\frac13+\frac14\right)+\left(\frac15+\frac16+\frac17+\frac18\right)+\dots+\left(\frac1{2^{n-1}+1}+\dots+\frac1{2^n}\right) \\&\ge 1+\left(\frac12\right)+\left(\frac14+\frac14\right)+\left(\frac18+\frac18+\frac18+\frac18\right)+\dots+\left(\frac1{2^n}+\dots+\frac1{2^n}\right) \\&=1+\frac12+\frac24+\frac48+\dots+\frac{2^{n-1}}{2^n} \\&=1+n\cdot\frac12. \end{align}