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.

Solution 1:

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}$.

Solution 2:

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.