Exercise 801Combinatorics › Binomial coefficientsHigh schoolAdded 3 Nov 2026

Combinatorial proof

#combinatorial proof#binomial#choice

Statement

Prove $\sum_{k=0}^{n}\binom{n}{k}=2^n$ by a combinatorial argument.

Hint

Each subset either includes or doesn't include each element.

Show solutionHide solution

Combinatorial. For each element of an $n$ -set, we choose "in" or "out" — $2$ choices per element, giving $2^n$ subsets.

Algebraic. Setting $x=y=1$ in $(x+y)^n=\sum\binom{n}{k}x^{n-k}y^k$ .

Conclusion. $\sum_k\binom{n}{k}=2^n$ .