# 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?

• Note that $2^1=2$. – Balloon Jan 11 '17 at 23:02
• The case $n=1$ is $$\sum_{i=1}^2\frac1i=\frac11+\frac12\ge\cdots$$ – user228113 Jan 11 '17 at 23:02

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.

• Now I'm curious how this is going to end. During the induction step, does the following reasoning hold: ${\sum\limits_{i=1}^{2^{n+1}}} \frac{1}{i} \ge 1 +\frac{n}{2}+\frac{1}{2^{n+1}}\geq 1+\frac{n}{2}$ – emka Jan 11 '17 at 23:30
• I don't think you wrote the inequality you want to prove! check that ;) – RGS Jan 11 '17 at 23:33
• I got ya, there should be an $n+1$ in that middle piece. – emka Jan 12 '17 at 0:05
• @emka indeed; did you manage to finish it? – RGS Jan 12 '17 at 0:29
• I'm wondering if you did as well – Shawn Javadi Jan 12 '17 at 0:30

Neither: the question is not wrong and you are also not going insane ... You just made a little mistake. :)

• It was a binary question; are you sure we should disregard the Law of the Excluded Middle? ;) – Wildcard Jan 12 '17 at 3:09
• @Wildcard Well, either we disregard it or we don't. :) – Bram28 Jan 12 '17 at 3:23