# Proof by induction of summation inequality

Prove by induction the summation of $\frac1{2^n}$ is greater than or equal to $1+\frac{n}2$.

We start with $$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\dots+\frac1{2^n}\ge 1+\frac{n}2$$ for all positive integers.

I have resolved that the following attempt to prove this inequality is false, but I will leave it here to show you my progress. In my proof, I need to define P(n), work out the base case for n=1, and then follow through with the induction step. Strong mathematical induction may be used.

This is equivalent to $$\sum_{k=0}^n\frac1{2^k}\ge 1+\frac{n}2\;.$$

Let $P(n)$ be summation shown above.

Base case for $n=1$, the first positive integer,

$$\sum_{k=0}^1\frac1{2^k}=\frac1{2^0}+\frac1{2^1}=1+\frac12=\frac32\ge 1+\frac12=\frac32\;,$$

so base case is true.

Induction step: Assume $P(n)$ is true and implies $P(n+1)$. Thus

$$\sum_{k=0}^{n+1}\frac1{2^k}\ge\frac1{2^{n+1}}+\sum_{k=0}^n\frac1{2^k}\ge 1+\frac{n+1}2\;.$$

This can be written as

$$\sum_{k=0}^{n+1}\frac1{2^k}\ge \frac1{2^{n+1}}+1+\frac{n}2\ge 1+\frac{n+1}2\;.$$

I work the math out but I get stuck contradicting my statement. Please show your steps hereafter so I can correct my mistakes.

-
Please check that I didn’t make any inadvertent changes when I added $\LaTeX$ to your post. –  Brian M. Scott Mar 3 '12 at 17:17
You’re not trying to reach a contradiction: you’re trying to show that if $P(n)$ is true, then $P(n+1)$ is true. –  Brian M. Scott Mar 3 '12 at 17:19
Thanks for adding the LaTex. I know I should be proving the summation is true but my math always results in a contradiction. I guess I'm not manipulating the terms correctly. Got any tips? –  Jared Mar 3 '12 at 17:27
1+1/2+1/4=7/4 but 1+2/2 = 2 <7/4, thus, what you are trying to prove is false for n=2. –  Paxinum Mar 3 '12 at 17:35
@Pax: $2 < 7/4$? Indeed, it is false, but not because $2 < 7/4$. –  TMM Mar 3 '12 at 19:31

I think that your notation is rather badly confused: I strongly suspect that you’re supposed to be showing that $$\sum_{k=1}^{2^n}\frac1k\ge 1+\frac{n}2\;,\tag{1}$$ from which one can conclude that the harmonic series diverges. The basis step for your induction should then be to check that $(1)$ is true for $n=0$, which it is: $$\sum_{k=1}^{2^n}\frac1k=\frac11\ge 1+\frac02\;.$$

Now your induction hypothesis, $P(n)$, should be equation $(1)$, and you want to show that this implies $P(n+1)$, which is the inequality $$\sum_{k=1}^{2^{n+1}}\frac1k\ge 1+\frac{n+1}2\tag{2}\;.$$ You had the right idea when you broke up the bigger sum into the old part and the new part, but the details are way off:

\begin{align*}\sum_{k=1}^{2^{n+1}}\frac1k&=\sum_{k=1}^{2^n}\frac1k+\sum_{k=2^n+1}^{2^{n+1}}\frac1k\\ &\ge 1+\frac{n}2+\sum_{k=2^n+1}^{2^{n+1}}\frac1k\tag{3} \end{align*}

by the induction hypothesis $P(n)$. Now look at that last summation in $(3)$: it has $2^{n+1}-2^n=2^n$ terms, and the smallest of those terms is $\dfrac1{2^{n+1}}$, so $$\sum_{k=2^n+1}^{2^{n+1}}\frac1k\ge 2^n\cdot\frac1{2^{n+1}}=\frac12\;.$$ If you plug this into $(3)$, you find that $$\sum_{k=1}^{2^{n+1}}\frac1k\ge 1+\frac{n}2+\frac12=1+\frac{n+1}2\;,$$ which is exactly $P(n+1)$, the statement that you were trying to prove.

You’ve now checked the basis step and carried out the induction step, so you can conclude that $(1)$ is true for all $n\ge 0$.

-
I understand now that my summation notation was incorrect. However, the base case here is invalid because 0 is not a positive integer. Therefore the base case should start at n=1. –  Jared Mar 4 '12 at 18:44
@Izzy: It doesn’t really matter: the result is true for $n=0$, so there’s no harm starting there. –  Brian M. Scott Mar 5 '12 at 5:33

The base case looks okay. For the inductive step, you want to assume $P(n)$ is true, and you need to show that $P(n) \rightarrow P(n+1)$. Your wording suggests that you are assuming that implication.

So, you assume for all $k \geq 1$

$$\sum\limits_{i=0}^{k} \frac{1}{2^i} \geq 1 + \frac{k}{2}.$$

Then we have the following when $n = k + 1$

$$\sum\limits_{i=0}^{k+1} \frac{1}{2^i} = \frac{1}{2^{k+1}} + \sum\limits_{i=0}^{k} \frac{1}{2^i} \geq \frac{1}{2^{k+1}} + 1 + \frac{k}{2}.$$

We know that $\frac{1}{2^{k+1}} > \frac{1}{2}$, so we have

$$\sum\limits_{i=0}^{k+1} \frac{1}{2^i} \geq \frac{1}{2^{k+1}} + 1 + \frac{k}{2} > 1 + \frac{k+1}{2}.$$

Thus, for all $n \geq 1$, $P(n) \rightarrow P(n+1)$, so the hypothesis holds.

-
$\sum_{i\ge 0}\frac1{2^i}=2$, and the stated result is false for all sufficiently large $k$. –  Brian M. Scott Mar 3 '12 at 17:34
Oh I don't know where my mind went. I made a terrible mistake in saying that $\frac{1}{2^{k+1}} > \frac{1}{2}$. Just a stupid error. –  Kurtis Zimmerman Mar 3 '12 at 18:14

Hint:

$$\sum_{k=0}^n\frac1{2^k}=\frac{2^{n+1}-1}{2^n}$$

-
True, but it won’t help the OP, since the result that he stated is false (and almost certainly isn’t the one that he was actually supposed to prove). –  Brian M. Scott Mar 3 '12 at 17:36