Proof by induction $\sum_{k=1}^{2^n} \frac1k \ge 1 + \frac{n}2 $ Show that for all $n \in  N  , n \ge 1$ :
$\sum_{k=1}^{2^n}  \frac1k  \ge 1 + \frac{n}2 $
Here is what I got:
I. $A(1)$: $\sum_{k=1}^{2} \frac1k = 1.5 \ge 1.5 \;\;   \implies A(1) \text{ is correct}    $
II. $A(n)$ is correct:  $\sum_{k=1}^{2^n}  \frac1k  \ge 1 + \frac{n}2 $
III. Is $A(n+1)$ correct? $\sum_{k=1}^{2^n+1}  \frac1k  \ge 1 + \frac{n+1}2 $
IV.  Now I need the proof but I don't get the solution for it. Trying for hours - so hope someone can give me an answer with a reasonable explanation. Thank you very much! 
 A: Hint:
It is sufficient to show that
\begin{align*}
\sum_{k = 2^n + 1}^{2^{n + 1}} \frac{1}{k} \geq \frac{1}{2}.
\end{align*}
Note that each summand is not less than $\frac{1}{2^{n + 1}}$ and how many summands are there?
A: Base case: 
Let $n=1$. Then $\sum_{k=1}^{2^1} \frac{1}{k} \geq 1 + \frac{1}{2}$ by evaluation / inspection.
Induction step (examining the $n+1$ case against the $n$ case): 
$(\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}$
$(1+\frac{n+1}{2}) - (1+\frac{n}{2}) = \frac{1}{2}$
We only need to prove that $(\sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k}) \geq \frac{1}{2}$.
Note that there are $2^n$ terms in the lefthand summation, where all values of $\frac{1}{k}$ are $\geq \frac{1}{2^{n+1}}$. 
Therefore $(\sum_{k=2^n+1}^{2^{n+1}} \frac{1}{k}) \geq (2^n)(\frac{1}{2^{n+1}}) \geq \frac{1}{2}$.
A: Non-inductive justification for future viewers: We know from calculus that $H_n > \ln n$ for $n\geq1$ (where $H_n$ is the $n$th harmonic number).  Thus, this is trying to prove that $H_{2^n} \geq 1 + \frac{n}{2}$.
Applying our inequality: $H_{2^n} \geq \ln(2^n) = n\ln(2)$.  Now, $n\ln(2)\geq1+\frac n 2$ for $n\geq\frac{2}{2\ln 2 - 1}\approx 5.17$. So, this is justification enough for $n\geq 6$.  The cases $n=0,\ldots,5$ may be exhaustively checked.
Why would this approach ever be useful?  Knowing that you can often "replace" $H_n$ with $\ln n$ is a nice trick for quickly determining if a statement is true or false for the long-run behavior of the inequality.  For instance, if the problem started "prove or disprove" instead of "prove."  Also, in some fields, we primarily care about what happens when $n$ is large (asymptotic behavior); that is, we wouldn't care that this approach doesn't prove the result for small values of $n$.
