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.

How does one find a simple expression of the one below applying the binomial theorem:

$$\sum_{k=1}^n k \cdot 2^k{ n \choose k}$$

Edit:

$\frac{d}{dx}(x^k)=kx^{k-1}$

$(1 + x)^n = \sum_{k=0}^n { n \choose k}x^k = \sum_{k=0}^n { n \choose k}\frac{d}{dx}(x^k) = \sum_{k=0}^n { n \choose k}kx^{k-1} $

$n(1+x)^{n-1} = \sum_{k=1}^n k{ n \choose k}x^{k-1}$

Edit 2:

$nx(1+x)^{n-1} = \sum_{k=1}^n k{ n \choose k}2^{k}$

if substitute x = 2

$2n(1+2)^{n-1} = \sum_{k=1}^n k{ n \choose k}2^{k} $

Is this correct?

share|improve this question
    
Is this homework? –  Aryabhata Sep 22 '10 at 5:08
    
Yes, it is homework, however I dont need to turn it in. Just for learning purposes :) Am I suppose not to ask hw questions? I checked the FAQ but didn't find anything related w/ hw. –  Mike Sep 22 '10 at 5:10
    
If it is homework, you should at least show where you are stuck. Just posting the question without a hint of even having worked on it is frowned upon. –  Aryabhata Sep 22 '10 at 5:12
    
@Mike: homework is not exactly encouraged, although you're right that nothing in the FAQ states this explicitly. Generally you should tell us what you've done so far and what you're stuck on; that will make it more likely that people will try to help you. –  Qiaochu Yuan Sep 22 '10 at 5:12
    
@Qiaochu Yuan: so far I understand that I have to take the first and second derivative to make it similar to the binomial thm? However, I'm not quite sure how to set it up. Perhaps, if you could help me out with a different example but similar-idea that can guide me through, will be appreciated. –  Mike Sep 22 '10 at 5:26

1 Answer 1

up vote 3 down vote accepted

Since this looks like homework, I won't tell you how to do it with the binomial theorem and will tell you how to do it bijectively instead. How many ways are there to choose a committee of $k$ people out of $n$ people, split the committee into Democrats and Republicans, then elect a President from that committee, for some $k$?

On the one hand, the answer is $\displaystyle \sum_{k=1}^{n} k \cdot 2^k {n \choose k}$. On the other hand, one can first choose the President, then split the non-Presidents into Democrats, Republicans, and people not on the committee, then choose a party for the President, which can be done in $2n \cdot 3^{n-1}$ ways.


As for how to do it through the binomial theorem, here is a different but related application. Recall the geometric series formula

$$\frac{1}{1 - x} = \sum_{k=0}^{\infty} x^k.$$

What happens if we take the derivative of both sides? We get

$$\frac{1}{(1 - x)^2} = \sum_{k=1}^{\infty} kx^{k-1}.$$

Substituting $x = \frac{1}{2}$, we then conclude that

$$\sum_{k=1}^{\infty} \frac{k}{2^{k-1}} = 4.$$

This problem requires essentially the same trick.

share|improve this answer
    
@Mike: as for a hint on how to do this with the binomial theorem, replace 2 by x in the above proof and think about it for a bit. –  Qiaochu Yuan Sep 22 '10 at 5:22

Your Answer

 
discard

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