Exercise 315Combinatorics › Binomial coefficientsL1Added 30 Oct 2026

Sum of binomial coefficients

#binomial#counting

Statement

Prove that $\displaystyle\sum_{k=0}^{n}\binom nk=2^n$ in two ways: by computation, then by a counting argument.

Hint

Expand $(1+1)^n$ . For counting, think of subsets of an $n$ -element set.

Show solutionHide solution

Solution

Computation. By the binomial theorem, $2^n=(1+1)^n=\sum_{k=0}^n\binom nk$ .

Counting. $\binom nk$ is the number of $k$ -element subsets of an $n$ -element set. Summing over $k$ counts all subsets. Each element is either in or out of a subset, which gives $2^n$ subsets.

Sum of binomial coefficients

Statement

Solution

More problems in Binomial coefficients