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.

I am attempting to solve a problem that I posed myself, but I can't figure out how to simplify the solution from the "messy" state in which it currently exists. My mathematical background does not yet contain calculus or related studies, so it is quite likely there is a simple formula or theorem that can be applied that I do not know. I know the solution (because of Wolfram Alpha), but I am interested in determining how to solve it, and similar problems as they present themselves, by myself. The expression is:

$n+\displaystyle\sum\limits_{a=0}^{n-1}a\cdot2^{n-a-1}$

This is equal to $2^n-1$, according to Wolfram Alpha. How do I arrive at that solution? I greatly appreciate any help you can provide me on this problem. Thank you for your time and for any assistance you can give.

share|improve this question
    
@Sesquipedalian I edited your question, I changed "equivalent" to "equal". Statements are equivalent. The entities you're dealing with aren't statement but rather natural numbers. –  Git Gud Feb 20 '13 at 22:31
    
@Sesquipedalian Do you know about mathematical induction? –  Git Gud Feb 20 '13 at 22:32
    
@GitGud Sorry about that; I didn't realize the distinction was important. I don't know what you mean about the entities being natural numbers, though; aren't natural numbers integers? I know about basic induction, but by no means all there is to know. –  Matthew Tyler Feb 20 '13 at 22:33
    
They are indeed integers. Ignore my statement about them being natural numbers (even though it is true that natural numbers are integers). Just think about it as integers if you find it easier. –  Git Gud Feb 20 '13 at 22:42
    
Why are they considered integers, though if they are in terms of one or more variables? Doesn't that separate them from integers? –  Matthew Tyler Feb 20 '13 at 22:44
show 2 more comments

4 Answers

up vote 2 down vote accepted

In your sum, the term with $a=0$ is $0$. Take out the common factor $2^{n}$. And let $n=10$, for concreteness. So we want to find the sum $$S=\frac{1}{2^2}+\frac{2}{2^3}+\frac{3}{2^4}+\cdots +\frac{9}{2^{10}},$$ using a "general" method. Multiply $S$ by $2$. We get $$2S=\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots +\frac{9}{2^{9}}.$$ Write the expression for $S$ under the expression for $2S$, but pushed forward by one, so that the denominators line up nicely. Then the numerators are offset by $1$. Subtract. We get $$2S-S=S=\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\cdots +\frac{1}{2^9}-\frac{9}{2^{10}}.$$ Note that everything but the last term is a finite geometric series. I imagine you know how to find a closed form expression for that. If you don't, a simpler version of the same trick will do it.

Now that you know what's going on, repeat for general $n$, and simplify to taste.

Remark: $1.$ There was no need to get rid of the $2^n$. In fact things look much nicer if you don't: No denominators! I am in retrospect very unhappy about getting rid of it. Repeat my argument using $T=1\cdot 2^n+2\cdot 2^{n-1}+3\cdot 2^{n-2}+\cdots +(n-1)\cdot 2^0$. It will quite a bit prettier.

$2.$ Note that this is a distant relative of the so-called Gauss trick for finding the sum $1+2+3+\cdots +100$. The same idea works for a sum of shape $\sum_1^{n-1} kx^{k-1}$, if $x\ne 1$. You can adapt the idea to deal with $\sum_1^{n-1}k^2 x^k$, and other related sums.

share|improve this answer
    
Thanks a ton for the comprehensive solution! Can you please go into a bit more detail about the "simplification to taste?" –  Matthew Tyler Feb 20 '13 at 23:04
    
Before I do that, why don't you do the work in the style I describe at the beginning of the Remark. Very little simplification will be needed. –  André Nicolas Feb 20 '13 at 23:10
    
Ah, I just noticed that. You are right. The simplification does become much simpler. If I have any more trouble, I'll let you know, but I doubt I will. Thanks! –  Matthew Tyler Feb 20 '13 at 23:11
add comment

Proof it by induction, for $n=1$ it is true, than assume it is true for $n$ and show that this implies it is true for $n+1$ \begin{align*} n+1+ \sum_{a=0}^n a \cdot 2^{n-a} &=n +1 +2 \cdot \left(\sum_{a=0}^{n-1} a \cdot 2^{n-a-1}\right)+ n\\ &= 2 (2^n-1)+1\\ &=2^{n+1} -1 \end{align*}

share|improve this answer
    
This is just half the solution. It's just the way of confirming when you already have a hunch what the solution might be. The really difficult part in these problems, however, is always how to come up with the solution candidate. Do you know anything better than brute force and educated guessing? –  Arthur Feb 20 '13 at 22:37
    
@DominicMichaelis Thanks for the response. Can you please elaborate a bit more on the solution by showing how it being true for n means it is true for n+1? –  Matthew Tyler Feb 20 '13 at 22:38
    
look at it :) @arthur oh yeah –  Dominic Michaelis Feb 20 '13 at 22:44
    
@Arthur Do you know of any better way of solving it without already knowing the solution? Dominic Michaelis, thanks for the elaboration. –  Matthew Tyler Feb 20 '13 at 22:45
    
@MatthewTyler No, I do not. It frustrates me, but as far as I know, you'll just have to see that you're summing powers of two, so the sum should be something containing a power of two. Then calculate a few terms by hand, see how far off you are, and try to add terms to correct it. –  Arthur Feb 21 '13 at 7:59
add comment

Hint: Try writing the powers of two in binary, then sum up the terms starting with the least significant binary part and take a look at the carry-overs. Try some specific, small $n$ first.

share|improve this answer
add comment

You can solve it by splitting the sum and applying the formula for the geometric series $$\sum_{i=0}^n q^i = \frac{q^{n+1}-1}{q-1}$$ with $q=2$ two times on the result: \begin{align} \sum_{a=1}^{n-1} a 2^{n-a-1} &= 1\cdot 2^{n-2} + 2\cdot 2^{n-3} + \cdots + (n-1) 2^0 \\ &=(2^{n-2} + \cdots + 2^0) + ( 2^{n-3} + \cdots + 2^0) + (2^{n-4} \cdots + 2^0) + \cdots + (2^0)\\ &=(2^{n-1} -1) + (2^{n-2} -1) + \cdots + (2^1 - 1)\\ &=(2^{n-1} + 2^{n-2} + \cdots + 2^1) - (n-1)\\ &=(2^{n} - 2) - (n-1)\\ &=2^{n} - 1 - n\\ \end{align} Now add $n$ to both sides.

share|improve this answer
    
Isn't it basically the same as Andre's solution? –  tomasz Feb 20 '13 at 23:06
    
The exposition is substantially different. –  André Nicolas Feb 20 '13 at 23:12
    
In my view, an advantage of Andre's solution is that it is easier to generalise to other, similar structured problems, while I think my solution is more straightforward for the problem at hand. That's why I posted it. –  Elmar Zander Feb 21 '13 at 14:14
add comment

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.