Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks in advance

share|improve this question
1  
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. –  Emmad Kareem Sep 7 '12 at 21:33

3 Answers 3

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

share|improve this answer
    
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} $$

share|improve this answer
    
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*}$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.