Is this induction question wrong or am I going insane? Here's a question that I've come across: Prove by induction that for every integer $n$ greater than or equal to $1$,
$${\sum_{i=1}^{2^n}} \frac{1}{i} \ge 1 +\frac{n}{2}.$$
Now I know how to prove by induction, but wouldn't this fail $p(1)$ since
$$\frac{1}{1} \ge 1 +\frac{1}{2}$$ is not true?
 A: Neither: the question is not wrong and you are also not going insane ... You just made a little mistake. :)
A: Check the upper bound of the summation;
If $n = 1$, then we have
$$\sum_{i=1}^2 \frac1i = 1 + \frac12 \geq 1 + \frac12$$
which is definitely true.
Given the discussion in the comments, I expand my answer to include the induction proof as I would do it:
(PROOF BY INDUCTION:)
We already have the base case for $n = 1$; Assume it is true up to $k$. We show it is true for $k + 1$.
The summation becomes
$$\sum_{i=1}^{2^{k+1}} \frac1i = \sum_{i=1}^{2^k} \frac1i + \sum_{i=2^k+1}^{2^{k+1}} \frac1i \geq 1 + \frac{k}{2} + \sum_{i=2^k+1}^{2^{k+1}} \frac1i$$
which holds because of the induction step. We want to check if
$$1 + \frac{k}{2} + \sum_{i=2^k+1}^{2^{k+1}} \frac1k \geq 1 + \frac{k+1}{2} = 1 + \frac{k}{2} + \frac12$$
it suffices to show that
$$\sum_{i=2^k+1}^{2^{k+1}} \frac1i \geq \frac12$$
which is, indeed, true. Notice that every term on that series is greater than, or equal to, $\frac1{2^{k+1}}$:
$$\sum_{i=2^k+1}^{2^{k+1}} \frac1i \geq \sum_{i=2^k+1}^{2^{k+1}} \frac1{2^{k+1}} = 2^k\cdot \frac1{2^{k+1}} = \frac12$$
which concludes the proof.
