MathLabs
TheoremProved

Sum of the binomial coefficients

Statement

For every nonnegative integer nn: 2n=∑k=0n(nk)2^n=\sum_{k=0}^n\binom{n}{k}

Why is it true?

Setting aa and bb both equal to 11 in the binomial theorem turns every term an−kbka^{n-k}b^k into 11, so the whole sum collapses to a count of how many terms there are in total.

Proof sketch

Substitute a=1, b=1a=1,\ b=1 into the binomial theorem (a+b)n=∑k=0n(nk)an−kbk(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k: the left side becomes (1+1)n=2n(1+1)^n=2^n, and the right side becomes ∑k=0n(nk)1n−k1k=∑k=0n(nk)\sum_{k=0}^n\binom{n}{k}1^{n-k}1^k=\sum_{k=0}^n\binom{n}{k}, since 11 raised to any power is 11.

Equating the two sides gives exactly 2n=∑k=0n(nk)2^n=\sum_{k=0}^n\binom{n}{k}.

This identity also has a direct combinatorial meaning: (nk)\binom{n}{k} counts the kk-element subsets of an nn-element set SS, so ∑k=0n(nk)\sum_{k=0}^n\binom{n}{k} counts every subset of SS of any size at all, i.e. the whole power set, which has exactly 2n2^n elements because each of the nn elements is independently either in or out of a subset.

Topics that use this theorem

Step-by-step proofs

No step-by-step proof yet for this theorem.