2
$\begingroup$

Given: $${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n$$

Prove the following in 2 ways.

$$ {n \choose 1} + 2 {n \choose 2} + 3 {n \choose 3} + \cdots + n{n\choose n} = n 2^{n-1}.$$

I have already figured out one:

$$ \sum_0^n k\binom{n}{k} $$

Makes up part of the computation for the expected size of a group if you randomly select items from the total. This expected value is half of the size of the total. Thus:

$$ \frac{\sum_0^n k\binom{n}{k}}{\sum_0^n \binom{n}{k}} = \frac{n}{2} $$

With the result that $\sum_0^n\binom{n}{k} = 2^n$, this gives:

$$ \sum_0^n k\binom{n}{k} = \frac{n}{2}2^n = n2^{n - 1} $$ Which then equals the RHS But I cannot figure out another way. Thanks for any help

$\endgroup$
  • $\begingroup$ See this question. You can get this by differentiating the binomial theorem. $\endgroup$ – lulu Jun 4 '16 at 14:33
  • $\begingroup$ @vadim123: Thank you for pointing this out, I thought that he wanted a proof for both expressions. $\endgroup$ – MrYouMath Jun 4 '16 at 14:41
2
$\begingroup$

$$ \sum_{k=0}^n k\binom{n}{k} = \sum_{k=1}^n \frac{k n!}{k!(n-k)!} \\= \sum_1^n \frac{n!}{(k-1)!(n-k)!} \\ =n\sum_1^n \frac{(n-1)!}{(k-1)!(n-k)!} \\ =n\sum_0^{n-1} \frac{(n-1)!}{k!(n-1-k)!} \\ =n2^{n-1} $$

$\endgroup$
2
$\begingroup$

Second way can be done by blowing apart the binomials: $$\frac{k}{n}{n\choose k}=\frac{k}{n}\frac{n!}{(n-k)!k!}=\frac{(n-1)!}{(n-k)!(k-1)!}={n-1\choose k-1}$$ Now sum those up from $k=1$ to $k=n$ and you will get $2^{n-1}$.

Differentiating the binomial theorem is the "first way". OP's method is actually a third way, a nice combinatorial proof.

$\endgroup$
  • $\begingroup$ Thank you very much, if you could, could you please explain the first way of differentiating the binomial theorem as I actually don't know how to do that. $\endgroup$ – user344569 Jun 4 '16 at 14:41
  • $\begingroup$ See @david holden's solution for that method. $\endgroup$ – vadim123 Jun 4 '16 at 14:55
2
$\begingroup$

We are going to count the number of ways of making a team of any size less or equal to $n$ and then choose one as the leader of the team.

If the team is of size $k$ then the number of ways is $k{n\choose k}$. If the size of the team is not determined then we have $\sum_{k=1}^n k{n\choose k}$ ways.

The other counting is by first selecting the leader. Since there are $n$ people there are $n$ ways to select the leader. Then among the remaining $n-1$ people we can choose any subset of those $n-1$ people in $2^{n-1}$ ways to make a team. So in total we have $n\cdot 2^{n-1}$ ways.

$\endgroup$
1
$\begingroup$

Hint what's the derivative of original equation. Using derivatives can be one of the second way.

$\endgroup$
1
$\begingroup$

$$ (1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k \\ n(1+x)^{n-1} = \sum_{k=1}^n k \binom{n}{k}x^{k -1} $$ set $x=1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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