1
$\begingroup$

$$ \sum_{i=0}^n {n \choose i} i = n2^{n-1} $$

I am having trouble formulating a combinatorial proof.

An algebraic proof is quite simple, where one expands $(1 + x)^{n}$ and then takes the derivative. Any help with the combinatorial proof would be greatly appreciated.

$\endgroup$
0

2 Answers 2

Reset to default
5
$\begingroup$

Hint: Say there're $n$ people and you want to choose a group of $i$ and from that group a leader. So the number of ways is $\binom{n}{i}i.$ Instead you could choose a leader first, out of $n$ people, then choose other $i-1$ members for the group (leader is of course a member of the group). What's the number of ways for doing so? can you conclude the result then?

$\endgroup$
2
  • $\begingroup$ Ah! I knew it was something really simple. Just couldn't get my head around it. The 'leader' analogy really helped me out. Thanks! $\endgroup$
    – Zee
    Dec 4, 2014 at 5:38
  • $\begingroup$ @Zee, glad it was helpful. Cheers $\endgroup$
    – Ehsan M. Kermani
    Dec 4, 2014 at 5:40
0
$\begingroup$

Enumerate the list of all $2^n$ subsets of $n$ objects. For each of the $n$ objects, the number of subsets it appears in is $2^{n-1}$, so the total number of {subset, subset member} pairs is $n2^{n-1}$. On the other hand, each of the $\binom{n}{i}$ subsets of size $i$ contributes $i$ {subset, subset member} pairs.

$\endgroup$
1
  • $\begingroup$ This is also a really good alternate explanation, just a little harder to grasp than the one mentioned above. $\endgroup$
    – Zee
    Dec 4, 2014 at 5:41

Not the answer you're looking for? Browse other questions tagged .