2

Prove by induction $\sum \frac {1}{2^n} < 1$

Well supposing the base case has been shown to be true, I start with the induction step:

Suppose true for n = k:

$$ \frac{1}{2} + \frac{1}{4} + ....\frac{1}{2^k} < 1$$

Want to show this is true for: $$ \frac{1}{2} + \frac{1}{4} + ....\frac{1}{2^k} + \frac{1}{2^{k+1}} < 1$$

Now this is where i am getting stuck, should i be tryig to show that $$ \frac{1}{2} + \frac{1}{4} + ....\frac{1}{2^k} + \frac{1}{2^{k+1}} < 1 +\frac{1}{2^{k+1}}$$ or should i be attempting to show that $1 + \frac{1}{2^{k+1}} < 1$ which is utter nonsense. So i am stuck on what exactly to prove here.

Note i also thought of maybe using the geometric series of $\frac {1}{2} $ as some upper bound but then that would provide me a value that was greater than 1 so it didn't work out

D.C. the III
  • 5,619
  • 1
    Show something stronger. Show that the sum is $= 1 - a_k$ for some specific positive $a_k$, or that it is $< 1-b_k$. – Daniel Fischer Sep 23 '15 at 20:30
  • I gather what to do based on the hint Umberto gave below, but I am curious as to why this is a stronger result ? Is this because of the strict equality? – D.C. the III Sep 23 '15 at 20:34
  • 1
    Yes. An equality gives you more information than an inequality, so it's stronger (when the two are compatible). You can deduce the inequality from the equality, but not vice versa. The point is that the stronger result gives you more to work with in the induction step. – Daniel Fischer Sep 23 '15 at 20:55
  • @DanielFischer: See how to use induction directly to the inequality from my answer ;) – f10w Sep 23 '15 at 21:05
  • That's a pretty nice idea, @Khue. – Daniel Fischer Sep 23 '15 at 21:15

2 Answers2

14

For $n=k+1$:

$$\frac{1}{2} + \frac{1}{4} + ....\frac{1}{2^k} + \frac{1}{2^{k+1}} = \frac{1}{2} + \frac{1}{2}\left(\frac{1}{2} + \frac{1}{4} + ....\frac{1}{2^k}\right) < \frac{1}{2} + \frac{1}{2}\times 1 =1.$$

f10w
  • 4,509
  • 15
  • 22
4

Use induction to prove that $$\frac 12 + \frac 14 + \cdots + \frac 1{2^n} = 1 - \frac{1}{2^n}$$ for all $n$. This will give you the result immediately since $1 - \frac{1}{2^n} < 1$.

Umberto P.
  • 52,165
  • 1
    Proof: If $n=1$, then $\frac{1}{2} = 1 - \frac{1}{2^1} = \frac{1}{2} $. Assume it is true that $\frac{1}{2} + \frac{1}{2^2} + ... + \frac{1}{2^k} = 1 - \frac{1}{2^k}$. Then, we have

    $$ \frac{1}{2} + \frac{1}{2^2} + ... + \frac{1}{2^k} + \frac{1}{2^{k+1}} = 1 - \frac{1}{2^k} + \frac{1}{2^{k+1}} = 1 - \frac{2^{k+1}-2^k}{2^k \cdot 2^{k+1}} = 1 - \frac{ 2^k }{2^k} \frac{ 2 - 1}{2^{k+1}} = 1 - \frac{1}{2^{k+1}} $$

     –  Sep 23 '15 at 20:37
  • Even simpler: $$-\frac{1}{2^k} + \frac{1}{2^{k+1}} = - \frac{2}{2^{k+1}} + \frac{1}{2^{k+1}} = - \frac{1}{2^{k+1}}.$$ – Umberto P. Sep 23 '15 at 20:43