5
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – emka Jan 11 '17 at 23:30
  • $\begingroup$ I don't think you wrote the inequality you want to prove! check that ;) $\endgroup$ – RGS Jan 11 '17 at 23:33
  • $\begingroup$ I got ya, there should be an $n+1$ in that middle piece. $\endgroup$ – emka Jan 12 '17 at 0:05
  • $\begingroup$ @emka indeed; did you manage to finish it? $\endgroup$ – RGS Jan 12 '17 at 0:29
  • $\begingroup$ I'm wondering if you did as well $\endgroup$ – Shawn Javadi Jan 12 '17 at 0:30
8
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.