# 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? – ithisa 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
• So its basically sum of lengths of all possible subsets... – Maha Mar 10 '17 at 4:56

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

**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 LHS=RHS Proven **

Another possible interpretation is through the expected number of heads in $$n$$ tosses of a fair coin which is $$n/2$$.
That is, we shall have $${n \over 2} = \sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,n} \right)} {i\left( \matrix{ n \cr i \cr} \right)\left( {{1 \over 2}} \right)^{\,i} \left( {{1 \over 2}} \right)^{\,n - i} } = {1 \over {2^{\,n} }}\sum\limits_{\left( {0\, \le } \right)\,i\,\left( { \le \,n} \right)} {i\left( \matrix{ n \cr i \cr} \right)}$$

Assume :

You have $$n$$ beads, numbered $$1$$ to $$n$$, of same mass $$=1$$.

1)$$\binom{n}{i}$$ is the number of distinct sets of $$i$$ beads, where $$i=0,1,2,...n.$$

Every set of $$i$$ beads has a mass $$i\cdot1$$, there are $$\binom{n}{i}$$ of them, hence their total mass:

$$T:= \sum_{i=0}^{n}\binom{n}{i}i\cdot 1.$$

2)Separate bead $$1$$ and consider the total number of sets that can be formed with the remaining $$n-1$$ beads: $$2^{n-1}$$.

Hence adding bead $$1$$ to each of the above sets we conclude:

Bead $$1$$ is present in $$2^{n-1}$$ sets out of the $$2^n$$ original sets.

Bead $$1$$ contributes $$2^{n-1} \cdot 1$$ to $$T$$, so do the beads $$2,3,...n$$.

Hence : $$T=n2^{n-1}\cdot 1$$.