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

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

• 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? – dc3rd Sep 23 '15 at 20:34
• 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 ;) – Khue Sep 23 '15 at 21:05
• That's a pretty nice idea, @Khue. – Daniel Fischer Sep 23 '15 at 21:15

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$.
• 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}}$$ – user203867 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
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.$$