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