2
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Show something stronger. Show that the sum is $= 1 - a_k$ for some specific positive $a_k$, or that it is $< 1-b_k$. $\endgroup$
    – Daniel Fischer
    Commented Sep 23, 2015 at 20:30
  • $\begingroup$ 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? $\endgroup$
    – D.C. the III
    Commented Sep 23, 2015 at 20:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Daniel Fischer
    Commented Sep 23, 2015 at 20:55
  • $\begingroup$ @DanielFischer: See how to use induction directly to the inequality from my answer ;) $\endgroup$
    – f10w
    Commented Sep 23, 2015 at 21:05
  • $\begingroup$ That's a pretty nice idea, @Khue. $\endgroup$
    – Daniel Fischer
    Commented Sep 23, 2015 at 21:15

2 Answers 2

Reset to default
14
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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}} $$ $\endgroup$
    – user203867
    Commented Sep 23, 2015 at 20:37
  • $\begingroup$ 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}}.$$ $\endgroup$
    – Umberto P.
    Commented Sep 23, 2015 at 20:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .