Exercise 1607Combinatorics › Counting principlesOlympiadAdded 3 Nov 2026

Double counting

#double counting#combinatorial proof#count in two ways

Statement

Show that $\sum_{k=0}^n\binom{n}{k}=2^n$ by double counting.

Hint

Count subsets of an $n$ -element set in two ways.

Show solutionHide solution

First way. Number of subsets of $\{1,\ldots,n\}$ is $2^n$ (each element in or out).

Second way. Group subsets by size: $\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}$ .

Conclusion. Both equal the number of subsets, so $\sum\binom{n}{k}=2^n$ .