Sum of Binomial Coefficients over Lower Index/Proof 2

Theorem

$\ds \sum_{i \mathop = 0}^n \binom n i = 2^n$

Proof

Let $S$ be a set with $n$ elements.

From the definition of $r$-combination, $\ds \sum_{i \mathop = 0}^n \binom n i$ is the total number of subsets of $S$.

Hence $\ds \sum_{i \mathop = 0}^n \binom n i$ is equal to the cardinality of the power set of $S$.

Hence the result.

$\blacksquare$

Sources

• 1965: Seth Warner: Modern Algebra ... (previous) ... (next): Chapter $\text {III}$: The Natural Numbers: $\S 19$: Combinatorial Analysis: Theorem $19.9$