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.

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

Solution 2:

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.

Solution 3:

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$

Solution 4:

$$\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*} \\ $$