# Summation equation for $2^{x-1}$

Since everyone freaked out, I made the variables are the same. $$\sum_{x=1}^{n} 2^{x-1}$$

I've been trying to find this for a while. I tried the usually geometric equation (Here) but I couldn't get it right (if you need me to post my work I will). Here's the outputs I need:

1, 3, 7, 15, 31, 63

If my math is correct.

-
Don't you mean $$\sum_{i=1}^n 2^{i-1}$$? – Pedro Tamaroff Aug 8 '12 at 4:15
That thing you have there sure ain't convergent... – J. M. Aug 8 '12 at 4:18
You don't mean to sum just $n$ terms ? – Belgi Aug 8 '12 at 4:53
Changed that $\infty$ to $n$. – Dilip Sarwate Aug 8 '12 at 11:48

Use the equation for the sum of a geometric series: $$\sum_{i=1}^n a\cdot r^{i-1}=\frac{a(r^n-1)}{r-1}$$ where $a$ is the initial value of the sequence $u_n=a\cdot r^{n-1}$ and $r\ne1$. In your specific case the equation becomes:

$$\frac{1\cdot(2^n-1)}{2-1}=2^n-1$$ So the sum of the first $n$ terms is $2^n-1$

-

In this instance, without explicitly using the formula for geometric series, \begin{align*} \sum_{x=1}^n 2^{x-1} &= 1 + 2 + 2^2 + 2^3 + \cdots + 2^{n-1}\\ &= 1 + (1 + 2 + 2^2 + 2^3 + \cdots + 2^{n-1}) - 1 &\text{add and subtract}~ 1\\ &= (1 + 1) + (2 + 2^2 + 2^3 + \cdots + 2^{n-1}) - 1 &\text{regroup}\\ &= 2 + (2 + 2^2 + 2^3 + \cdots + 2^{n-1}) - 1\\ &= (2 + 2) + (2^2 + \cdots + 2^{n-1}) - 1 &\text{regroup again}\\ &= 2^2 + (2^2 + 2^3 + \cdots + 2^{n-1}) - 1\\ &= (2^2 + 2^2) + (2^3 + \cdots + 2^{n-1}) - 1 &\text{regroup again}\\ &= 2^3 + (2^3 + \cdots + 2^{n-1}) - 1\\ &= \cdots &\text{lather, rinse, repeat}\\ &= 2^{n-1} + (2^{n-1}) - 1 &\text{nearly done}\\ &= 2^n - 1. \end{align*} Now that we know the form of the result, it is also possible to prove the result

$$\sum_{x=1}^n 2^{x-1} = 2^n - 1$$

more formally by induction. Clearly, the result holds when $n = 1$ since $2^0 = 2^1 - 1$. Then, if the result holds for some positive integer $n$, we have that

$$\sum_{x=1}^{n+1} 2^{x-1} = \sum_{x=1}^n 2^{x-1} + 2^n = (2^n-1) + 2^n = 2^{n+1} - 1$$ and so the result holds for $n+1$ as well. Since we know that the result holds when $n=1$, it follows by induction that it holds for all positive integers $n$.

-
"$\rm lather, rinse, repeat$" +1 – Pedro Tamaroff Aug 8 '12 at 14:41

You're saying you want as outputs

$1,3,7,15,31,63$

Note they are respectively $2^1-1,2^2-1,2^3-1,2^4-1,2^5-1,2^6-1$ so what you really want is $$f(n)=2^n-1$$

Now this is a finite geometric sum, namely

$$\sum_{i=0}^{n-1}2^i=2^n-1$$

This follows from the geometric sum formula, that is

$$\sum_{i=0}^{n-1} a^i=\frac{a^n-1}{a-1}$$

The MO for this is the following. Let our sum be $S$

$$1 + a + \cdots + {a^{n - 1}} = S$$

Then

$$a + {a^2} + \cdots + {a^n} = aS$$

But

$$a + {a^2} + \cdots + {a^n} = \left( {1 + a + \cdots + {a^{n - 1}}} \right) - 1 + {a^n} = S - 1 + {a^n}$$

So that

\eqalign{ & S - 1 + {a^n} = aS \cr & S - aS = 1 - {a^n} \cr & \left( {1 - a} \right)S = 1 - {a^n} \cr & S = \frac{{1 - {a^n}}}{{1 - a}} \cr}

as desired.

-

\begin{align*} \sum_{i=1}^{n} 2^{i-1} &= \sum_{i=0}^{n-1} 2^{i}\\ &=1+2+2^2 \cdots 2^{n-1} \\ &=\frac{2^{n}-1}{2-1} \quad \quad \text{(usual geometric series formula)} \\ &=2^n -1 \end{align*} \\

-
Why are you keeping the $x$ in the summands? – Pedro Tamaroff Aug 8 '12 at 4:25
@PeterTamaroff oh that was a mistake.Now I have corrected. – Saurabh Aug 8 '12 at 4:29

For sum upto $n$ terms $$\sum_{x=1}^n 2^{x-1}=\frac{\sum_{x=1}^n 2^x}{2}$$ Numerator is the usual geometric series $a,ar,ar^2,\cdots,ar^{n-1}$ which sum is $$\frac{a(r^n-1)}{r-1}$$ which gives $$\frac{\sum_{x=1}^n 2^x}{2}=\frac{2(2^n-1)}{2(2-1)}=2^n-1$$

-
Oh, oops, I did the equation wrong. It's supposed to be 2^(x-1) – Gᴇᴏᴍᴇᴛᴇʀ Aug 8 '12 at 4:13
Maybe you should edit your answer, or delete it entirely. – Dilip Sarwate Aug 8 '12 at 13:39