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
    @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