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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

This is not really an answer to the question (very good ones have already been given), but to the more daunting challenge of finding a 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 by$~2$ gives the desired equation $\sum_{i=0}^n\binom nii=L=n2^{n-1}$.

Answer 4

Consider an ordered $n+1-tuple$ of numbers,assigned to each subset of the set $S=\{1,2,3,...n,n+1\}$, whose $i$th coordinate is either $1$ or $0$ accordingly as the the $i$th object is chosen or not respectively. Clearly the left hand side of the equation gives the total number of $1$'s on all the possible $n+1-tuple$s. Again for every $k$ belonging to S a total of $2^n$ $1$s are contributed in those $n+1-tuple$s for $k$.Therefore total no. of $1$s contributed for all $n+1$ numbers is $(n+1)2^n$.Therefore $\mathrm{LHS=RHS}$ Proven.