# Sum of the sequence

What is the sum of the following sequence

\begin{align*} (2^1 - 1) &+ \Big((2^1 - 1) + (2^2 - 1)\Big)\\ &+ \Big((2^1 - 1) + (2^2 - 1) + (2^3 - 1) \Big)+\ldots\\ &+\Big( (2^1 - 1)+(2^2 - 1)+(2^3 - 1)+\ldots+(2^n - 1)\Big) \end{align*}

I tried to solve this. I reduced the equation into the following equation

$$n(2^1) + (n-1)\cdot2^2 + (n-2)\cdot2^3 +\ldots$$

but im not able to solve it further. Can any one help me solve this equation out. and btw its not a Home work problem. This equation is derived from some puzzle.

-
Note that your formula $n(2^1) + (n-1)\cdot2^2 + (n-2)\cdot2^3 +\ldots$ is not correct, for example, when n=2 it does not yield 5. – NoChance Sep 7 '12 at 21:33

We have \begin{align} \sum_{i=1}^n\sum_{j=1}^i(2^j-1) &=\sum_{i=1}^n\sum_{j=1}^i2^j-\sum_{i=1}^n\sum_{j=1}^i1\\ &=\sum_{i=1}^n(2^{i+1}-2)-\sum_{i=1}^ni\\ &=2\sum_{i=1}^n2^{i}-\sum_{i=1}^n2-\sum_{i=1}^ni\\ &=2(2^{n+1}-2)-2n-\frac12n(n+1)\\ &=2^{n+2}-4-\frac52n-\frac12n^2\\ \end{align}

-
Your formula fails for n=2, pls verify.. – Ravi Sep 7 '12 at 21:08
for n=2, the actual answer is 5 but your formula gives 9 – Ravi Sep 7 '12 at 21:08
@user70523 Looks like Eric fixed my mistake. The sum of powers of $2$ starting at $2^1$ rather than $2^0$ was the cause of my mistake. – alex.jordan Sep 7 '12 at 21:31
I got a downvote for this? If anyone was actually reading the answer the mistake was clear. – alex.jordan Sep 7 '12 at 21:34

Let's note that $$(2^1 - 1) + (2^2 - 1) + \cdots + (2^k - 1) = 2^{k+1} - 2-k$$ where we have used the geometric series. Thus, the desired sum is actually $$\sum_{k=1}^n{2^{k+1}-2-k}$$. As this is a finite sum, we can evaluate each of the terms separately. We get the sum is $$2\left(\frac{2^{n+1}-1}{2-1}-1\right) - 2n- \frac{n(n+1)}{2} = 2^{n+2}-4 - 2n-\frac{n(n+1)}{2}$$

-
Not sure why someone downvoted my correct answer... – Euler....IS_ALIVE Sep 7 '12 at 21:22
No one downvoted your correct answer. – Gigili Sep 7 '12 at 21:30
False. Someone did from "-1 30 mins ago downvoted Sum of the sequence" – Euler....IS_ALIVE Sep 7 '12 at 21:46
@Euler....IS_ALIVE The vote breakdown states that there are "+3 upvotes, 0 downvotes"? – Shaktal Sep 7 '12 at 22:01
@Euler: That's from you downvoting someone else's answer (downvoting answers costs 1 rep). If it was a downvote on your answer it would have been -2 rep. – hammar Sep 8 '12 at 2:17

Others have given the correct answer; here’s how you could have simplified your incorrect expression.

\begin{align*} n(2^1) + (n-1)\cdot2^2 + (n-2)\cdot2^3 +\ldots&=\sum_{k=1}^n(n-k+1)2^k\\ &=(n+1)\sum_{k=1}^n2^k-\sum_{k=1}^nk2^k\\ &=(n+1)\left(2^{n+1}-2\right)-\sum_{k=1}^n\sum_{i=1}^k2^k\\ &=(n+1)\left(2^{n+1}-2\right)-\sum_{i=1}^n\sum_{k=i}^n2^k\\ &=(n+1)\left(2^{n+1}-2\right)-\sum_{i=1}^n\left(2^{n+1}-2^i\right)\\ &=(n+1)\left(2^{n+1}-2\right)-n2^{n+1}+\sum_{i=1}^n2^i\\ &=(n+1)\left(2^{n+1}-2\right)-n2^{n+1}+2^{n+1}-2\\ &=2\cdot2^{n+1}-2n-4\\ &=2^{n+2}-2n-4 \end{align*}

-