17
$\begingroup$

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.

$\endgroup$
17
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Could you explain more why each element is in $2^{n-1}$ subsets? $\endgroup$ – ithisa May 13 '13 at 22:27
  • $\begingroup$ @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.) $\endgroup$ – Tom Oldfield May 13 '13 at 22:41
  • $\begingroup$ So its basically sum of lengths of all possible subsets... $\endgroup$ – Maha Mar 10 '17 at 4:56
37
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I really like this "committee" proof. Do you have any reference where such methods are used to prove more complicated sums? $\endgroup$ – Prism Jun 2 '13 at 1:36
  • 2
    $\begingroup$ @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. $\endgroup$ – Alexander Gruber Jun 2 '13 at 2:47
  • 1
    $\begingroup$ Thanks! This is exactly what I was looking for. :) $\endgroup$ – Prism Jun 2 '13 at 2:55
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

**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 **

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.