1
$\begingroup$

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.

  • 0
    @TMM Oh, I assumed that summation of 1/2^n was what any mathematician would think: 1+1/2+1/4+...+1/2^n.2012-03-05

3 Answers 3

6

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

  • 0
    What does the "smallest of those terms" mean? Where does 2^(n+1) - 2^n = 2^n come from?2017-05-11
0

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.

  • 0
    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.2012-03-03
-1

Hint:

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

  • 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).2012-03-03