# The sum of $\sum_{j=1}^{n}{2^{-j}}$

Find the sum and substantiate the answer:

$\sum_{j=1}^{n}{2^{-j}}=\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots+\frac{1}{2^n}$.

My attempt:

I see that $\sum_{j=1}^{n}{2^{-j}}=1$. I figure that I should prove this by induction but can't see how.

Questions:

1. Is it correct to say that the above infinite series converges to 1 as n goes to infinity?

2. How do I prove the sums value by induction? Are there other ways?

• You can't find it because the sum is $1-2^{-n}$ and not $1$. – Alex Fish Nov 3 '15 at 23:54

I see that $\sum_{j=1}^n 2^{-j}= 1$.

This is not true for any $n\in\mathbb{N}$.

Is it correct to say that the above infinite series converges to 1 as n goes to infinity?

Yes.

How do I prove this by induction?

Are you trying to prove the convergence of the infinite series or to find the closed form of the finite series for any $n\in\mathbb{N}$ ? Induction only works for the latter.

In any case, it suffices to find the closed form of the finite series. The convergence of the infinite series follows from taking the limit of the closed form.

Proposition: $\displaystyle\sum_{k=0}^n r^k = \frac{r^{n+1}-1}{r-1}\quad \forall n\in\mathbb{N}\quad$ (This is called geometric series.)

Proof 1: Call the proposition $P(n)$. Check that $P(1)$ is correct. Then assume $P(n)$ and prove $P(n+1)$.

• Assume $P(n)$; that is, $\sum_{k=0}^nr^k = \frac{r^{n+1}-1}{r-1}$.
• Then prove $P(n+1)$; that is, prove $\displaystyle\sum_{k=0}^{n+1}r^k = \frac{r^{n+2}-1}{r-1}$. This is done as follows: \begin{align*} \sum_{k=0}^{n+1}r^k &= \left(\sum_{k=0}^{n}r^k\right) + r^{n+1}\\ &= \frac{r^{n+1}-1}{r-1} + r^{n+1}\\ &= \frac{r^{n+2}-1}{r-1}. \end{align*}

Proof 2: \begin{align*} (1+ r +r^2+\dots+ r^n)(r-1) &= (1+ r +r^2+\dots+ r^n)r - (1+ r +r^2+\dots+ r^n)\\ &= (r^2 + r^3+\dots r^{n+1}) - (1+ r +r^2+\dots+ r^n)\\ &= r^{n+1}-1\\ \implies (1+ r +r^2+\dots+ r^n) &= \frac{r^{n+1}-1}{r-1} \end{align*}

Proof 3: Let $S(n) = \sum_{k=0}^n r^k$ \begin{align*} S(n+1) &= S(n) + r^{n+1}\\ &= \sum_{k=0}^{n+1}r^k\\ &= r^0 + \sum_{k=1}^{n+1}r^k\\ &= 1 + \sum_{k=1}^{n+1}r^k\\ &= 1 + r\sum_{k=0}^{n}r^k\\ &= 1 + rS(n) \end{align*} Solve $S(n)+r^{n+1} = 1+rS(n)$ to get $\displaystyle S(n)=\frac{r^{n+1}-1}{r-1}$

If $\|r\| < 1$, $\lim_{n\to\infty}r^n= 0$, and $$\lim_{n\to\infty}S(n)=\lim_{n\to\infty}\frac{r^{n+1}-1}{r-1} = \frac{0-1}{r-1} =\frac{1}{1-r}$$

For your problem, $r=\frac{1}{2}$ and the series starts at $k=1$ instead of $k=0$. So $\displaystyle\sum_{j=1}^n2^{-j} = \frac{1}{2}\sum_{j=0}^{n-1}2^{-j}$

Notice that (use induction) : $$\forall (a,b)\in\mathbb{R}^2,\forall n\in\mathbb{N},a^n-b^n=(a-b)\sum_{k=0}^{n-1}a^kb^{n-k}.$$ Then, setting $a$ to $2^{-1}$ and $b$ to $1$, one has : $$\sum_{k=0}^{n-1}2^{-k}=\frac{2^{-n}-1}{2^{-1}-1}.$$ From there you can conclude.

$1-x^{n+1}=(1-x)(1+x+x^2+...+x^n)$, so $(1+x+x^2+...+x^n)=\frac{1-x^{n+1}}{1-x}$. So $x^0+\sum_{j=1}^nx^j=\sum_{j=0}^nx^j=\frac{1-x^{n+1}}{1-x}$. Substitute $x=\frac{1}{2}$ and you get $\sum_{j=1}^n\frac{1}{2}^j=\frac{1-\frac{1}{2}^{n+1}}{1-\frac{1}{2}}-1=1-\frac{1}{2}^n$. Letting $n\to\infty$, you get $1$.