# 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$. Sep 23, 2015 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? Sep 23, 2015 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. Sep 23, 2015 at 20:55
• @DanielFischer: See how to use induction directly to the inequality from my answer ;)
– f10w
Sep 23, 2015 at 21:05
• That's a pretty nice idea, @Khue. Sep 23, 2015 at 21:15

## 2 Answers

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

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, 2015 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}}.$$ Sep 23, 2015 at 20:43