# Combinatorial proof of $\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$.

Prove that $$\sum^{n}_{i=1}\binom{n}{i}i=n2^{n-1}$$

I can't find counting interpretations for either of the sides. A hint of "if $S$ is a subset of $\{1, . . . , n\}$ and $S^\prime$ is its complement then $|S| + |S^\prime| = n$" was also given, but I still don't know how to begin.

-

Hint: consider the the set of all subsets of $\{1,2,\dots,n\}$ (of which there are $2^n$) and try to find the total sum of the sizes of the subsets in two different ways. For example, the possible subsets of $\{1,2\}$ are $\{\},\{1\},\{2\},\{1,2\}$. Then adding up the sizes of each subset gives $0+1+1+2 = 4$.

More explicitly, if we add up the sizes of all possible subsets of $[n]=\{1,2,\dots,n\}$, we can either:

$1)$ Note that there are $\binom{n}{i}$ subsets of size $i$ which gives that the total sum of sizes is

$$\sum_{i=1}^{n}\binom{n}{i}i$$

$2)$ Observe that each element is in $2^{n-1}$ subsets, and so contributes $2^{n-1}$ to the total sum. Thus the sum equals

$$n2^{n-1}$$

The value of the sum doesn't change regardless of how we do it, so the expressions must be the same.

-
Could you explain more why each element is in $2^{n-1}$ subsets? – user54609 May 13 '13 at 22:27
@Eric Certainly. I have two reasons, pick your favourite. $1)$ Each subset that contains a given element may or may not contain each of the other $n-1$ elements, so there are $2^{n-1}$ possible such sets, one "$2$" for each choice. (This approach is the same as one of the ways to prove that the number of subsets of $[n]$ is $2^n$.) $2)$ We can partition the set of subsets of $[n]$ into the sets that contain the given element and the sets that don't. There is an obvious bijection between these two partitions, so they must be the same size, $2^n/2=2^{n-1}$. (This is my preferred method.) – Tom Oldfield May 13 '13 at 22:41

We can interpret this combinatorially as the number of ways to form a committee (of any size) with one chairman out of a group of $n$ people.

From $n$ people we first pick a committee of size $i$, then choose one the $i$ committee members to be the chairman. There are ${n \choose i}$ options for the members of the committee, after which there are $i$ options for the chairman. If we sum over all $i$ from $1$ to $n$, that covers committees of all possible (nonzero) sizes. So, we have $\sum_{i=1}^n {n \choose i}i$.

On the other hand, we could first pick one person from the $n$ people to be the chairman. Then for each of the remaining unchosen $n-1$ people, they can be either in or out of the committee. That's $2^{n-1}$ possibilities. So, we have $n2^{n-1}$.

-
I really like this "committee" proof. Do you have any reference where such methods are used to prove more complicated sums? – Prism Jun 2 '13 at 1:36
@Prism The technique is called "double counting." Proofs from the Book by Ziegler has a chapter on cool double counting proofs, which has a partial preview here. – Alexander Gruber Jun 2 '13 at 2:47
Thanks! This is exactly what I was looking for. :) – Prism Jun 2 '13 at 2:55

This is not really an answer to the question (very good ones have already been given), but to the more daunting challenge of finding an way to actually use the hint given in the question (in an interesting way).

The left hand side $L=\sum_{i=0}^n\binom nii$ gives the sum of the sizes of all subsets of an $n$-element set, grouping together the $\binom ni$ subsets of size$~i$. Note that I've thrown in the empty set, which makes no difference for this sum, but makes the number of subsets summed over equal to $2^n$. Since taking the complement of all subsets again gives every subset exactly once (the operation is an involution), $L$ also gives the sum of the sizes of the complements of all subsets of an $n$-element set. But if a set has size $i$, then its complement has size $n-i$ (this is where the hint is used!) so this means that $L=\sum_{i=0}^n\binom ni(n-i)$. Adding up the two summations gives $$2L=\sum_{i=0}^n\binom ni(n+(n-i))=n\sum_{i=0}^n\binom ni=n2^n.$$ Dividing both sides gives the desired equation $\sum_{i=0}^n\binom nii=L=n2^{n-1}$.

-