1
$\begingroup$

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.

  • 0
    Changed that $\infty$ to $n$.2012-08-08

6 Answers 6

0

A very short 'proof':$\begin{align}2\sum_{x=1}^n2^{x-1}&=2^n+2^{n-1}+\dots+4+2\\-\left(\quad\sum_{x=1}^n2^{x-1}\right.&=\left.\phantom{2^n}\quad\ 2^{n-1}+\dots+4+2+1\vphantom{\sum_{x=1}^n2^{x-1}}\right)\\\hline\sum_{x=1}^n2^{x-1}&=2^n-1\tag{subtract the two}\end{align}$

  • 0
    @DilipSarwate It may not to you or I, but to someone who asked this question or who came here not knowing the answer, my answer may very well be more understandable to them. Quality is not always about content.2016-12-16
10

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

  • 1
    "$\rm lather, rinse, repeat$" +12012-08-08
6

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.

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$

2

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$

  • 1
    Maybe you should edit your answer, or delete it entirely.2012-08-08
2

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

  • 0
    @PeterTamaroff oh that was a mistake.Now I have corrected.2012-08-08