3
$\begingroup$

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?

  • 0
    Is this homework?2010-09-22
  • 0
    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.2010-09-22
  • 0
    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.2010-09-22
  • 0
    @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.2010-09-22
  • 0
    @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.2010-09-22
  • 0
    @Mike: I've given a different example in my answer.2010-09-22
  • 0
    @Mike: You're almost there!2010-09-22
  • 0
    @Qiaochu Yuan: How about my last edit?2010-09-22
  • 0
    @Mike: You've gotten it. :)2010-09-22

1 Answers 1

4

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.

  • 0
    @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.2010-09-22