Total size of all subsets of a set is $n\cdot2^{n-1}$ So I'm supposed to show that the total size of all subsets of a set is $n\cdot2^{n-1}$. I've noted that $2^{n-1}$ is the size of the power set of an $n-1$ element set, and I think it's that every element of $P(X)$ where $|X|=n-1$ will contribute $n$ to the size of the subsets of $P(X')$ where $|X'| = n$ but I don't know why or how. Can anyone help?
Thanks!
 A: Each subset and its complement together have exactly $n$ elements.
A: Imagine we have a list of all the subsets of the $n$-element set $A=\{a_1,a_2,\dots,a_n\}$.  We find the sum of their sizes in a funny way. 
Look first at $a_1$, and make a tick mark for every one of the subsets of $A$ that $a_1$ occurs in. We will make $2^{n-1}$ tick marks, since $2^{n-1}$ subsets of $A$ contain $a_1$.  
Do the same for all the $a_i$. The total number of tick marks is the sum of the sizes of the subsets of $A$. For given any subset $S$ of $A$, our procedure produces a tick mark for every member of $S$. 
The total number of tick marks is $n2^{n-1}$. 
Remark: We are evaluating the sum $\sum_{k=1}^n k\binom{n}{k}$. There are a number of proofs on MSE that this sum is $n2^{n-1}$. We described a counting argument specifically suited to the "sum of sizes" version.  
A: The other answers are more elegant.  But the most straightforward way is
$$
\sum_{i=0}^n {n \choose i} i
= \sum_{i=0}^n \frac{n! \cdot i}{i!(n-i)!}
= n \sum_{i=1}^n {n-1 \choose i-1}
= n 2^{n-1}
$$
A: $$f(x)=(1+x)^n=\sum_{k=0}^n{n\choose k}x^k\iff f'(x)=n\,(1+x)^{n-1}=\sum_{k=0}^nk{n\choose k}x^{k-1}$$
$$f'(1)=n\cdot2^{n-1}=\sum_{k=0}^nk{n\choose k}$$
A: The total size is $\#\{\,(x,S)\in X\times\mathcal P(X)\mid x\in S\,\}$ if you count by fixing each$~S\subseteq X$ first. But counting fixing each $x\in X$ first, it contributes $\#\mathcal P(X\setminus\{x\})=2^{n-1}$ to this size, for a total of $n2^{n-1}$.
