Processing math: 18%
ThmDex – An index of mathematical definitions, results, and conjectures.
Result R2621 on D2167: Binomial coefficient
Sum of binomial coefficients
Formulation 1
Let n,mN each be a D996: Natural number such that
(i) 0mn
Then \begin{equation} \sum_{m = 0}^n \binom{n}{m} = 2^n \end{equation}
Also known as
Cardinality of finite power set equals sum of cardinalities of sets of N-subsets
Proofs
Proof 0
Let X be a D11: Set such that
(i) \begin{equation} |X| = N \in \mathbb{N} \end{equation}
Let \mathcal{P}_n(X) denote the D2906: Set of N-subsets of X for 0 \leq n \leq N. Since \mathcal{P}(X) = \bigcup_{n = 0}^N \mathcal{P}_n(X), the results
(i) R1839: Cardinality of power set of a finite set
(ii) R1838: Cardinality of finite set union of finite sets
(iii) R1831: Real arithmetic expression for binomial coefficient

imply \begin{equation} 2^N = |\mathcal{P}(X)| = \left| \bigcup_{n = 0}^N \mathcal{P}_n(X) \right| = \sum_{n = 0}^N |\mathcal{P}_n(X)| = \sum_{n = 0}^N \binom{N}{n} \end{equation} \square