3
$\begingroup$

Must show: $\sum_{i=0}^n i{n \choose i} = n2^{n-1}$ using a combinatorial argument. I have tried picking the problem apart by determining that the summation is equal to 1/2 of the size of all subsets of a set of size n times n. But I am having trouble relating that to what each term of the summation represents.

$\endgroup$
6
$\begingroup$

Hint: We have a group of $n$ people. They want to form a committee of $1$ or more people (so size is elastic), with a specified Chair. We count the number of ways to form a Committee-with-named-Chair in two ways.

First way: We pick a Chair ($n$ choices). For each choice, we pick a subset of the remaining $n-1$ people to join her on the Committee. If we count in this way, we will get the right-hand side of the identity.

Second way: We pick a group of $i$ people, $i=1$ to $n$, and they choose a Chair among them. If we count in this way, we will get the left-hand side of the identity.

$\endgroup$
  • $\begingroup$ It really doesn't get much simpler than this. $\endgroup$ – Patrick Sep 29 '13 at 21:12

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.