Exercise 894Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Subset sums

#subset sums#double counting#average

Statement

Compute the sum of $|S|$ over all subsets $S$ of an $n$ -element set.

Hint

Each element is in exactly half the subsets.

Show solutionHide solution

Double count. Sum over subsets of their size = sum over elements of the number of subsets containing them.

Per element. Each element appears in $2^{n-1}$ subsets.

Total. $n\cdot2^{n-1}$ .

Conclusion. $\sum_S|S|=n\cdot2^{n-1}$ .

Check. $n=2$ : subsets $\varnothing,\{1\},\{2\},\{1,2\}$ , sizes sum to $0+1+1+2=4=2\cdot2=4$ . ✓