Prove by induction: $\frac{1}{2}+\frac{1}{4}+ \frac{1}{8}+ ... +\frac{1}{2^n} < 1$

Question

Prove by induction: for all $n > 1$

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

Answer 1

For $n = 1$, $\dfrac{1}{2} < 1$, so it is true. Assume it is true for $n = k \ge 1$, you show it is also true for $n = k+1$. You have: $\dfrac{1}{2}+\dfrac{1}{4} +\cdots +\dfrac{1}{2^{k+1}}= \dfrac{1}{2}+\dfrac{1}{2}\left(\dfrac{1}{2}+\dfrac{1}{4}+\cdots+\dfrac{1}{2^k}\right)< \dfrac{1}{2}+\dfrac{1}{2}\cdot 1 = 1$ by the inductive step $n=k$, so it is true for $n = k+1$, and hence is true for all $n \ge 1$.

Answer 2

Hint To to prove the stronger result $$\frac{1}{2}+ \frac{1}{4}+ \frac{1}{8}+ ... + \frac{1}{2^n} \leq 1-\frac{1}{2^n}$$

In fact you have equality above.

P.S. In many situations, if $a_n \geq 0$, and $C$ is a constant, we cannot prove by induction that $\sum_{k=1}^n a_k <C$. But we can in some cases find some $b_n \geq 0$ such that $$\sum_{k=1}^n a_k <C -b_n$$ is an easy induction exercise. My favourite is $$\sum_{k=1}^n \frac{1}{k^2} <2$$ where it is easy to prove that $$\sum_{k=1}^n \frac{1}{k^2} <2-\frac{1}{n}$$

Answer 3

HINT: Notice that $$\frac{1}{2^1}+\frac{1}{2^2}+...+\frac{1}{2^n}$$ $$=(2-1)\bigg(\frac{1}{2^1}+\frac{1}{2^2}+...+\frac{1}{2^n}\bigg)$$ $$=\frac{2}{2^1}-\frac{1}{2^1}+\frac{2}{2^2}-\frac{1}{2^2}+...+\frac{2}{2^n}-\frac{1}{2^n}$$ $$=1-\frac{1}{2^1}+\frac{2}{2^2}-\frac{1}{2^2}+...+\frac{2}{2^n}-\frac{1}{2^n}$$ $$=1-\frac{1}{2^1}+\frac{2}{2^2}-\frac{1}{2^2}+...+\frac{2}{2^n}-\frac{1}{2^n}$$ $$=1-\frac{1}{2^1}+\frac{1}{2^1}-\frac{1}{2^2}+...+\frac{2}{2^{n-1}}-\frac{1}{2^n}$$ Then cancel out all of the telescoping terms.