Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

up vote 4 down vote accepted

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$.

share|improve this answer
    
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.

share|improve this answer
    
$\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}$$

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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