(The first proof is a combinatorial argument.)

There are \(\binom{n}{k}\) subsets of size \(k\) of the set \(N = \{1, 2, 3, \ldots, n\}\). We will partition these \(k\)-subsets into two disjoint cases: those that contain the final number, \(n\), and those that do not.

Let \begin{equation*} A = \{ S \subseteq N \suchthat |S| = k \; \land \; n \notin S \} \end{equation*} and, let \begin{equation*} B = \{ S \subseteq N \suchthat |S| = k \; \land \; n \in S \}. \end{equation*}

Since the number \(n\) is either in a \(k\)-subset or it isn't, these sets are disjoint and exhaustive. So the addition rule tells us that \begin{equation*} \binom{n}{k} = |A| + |B|. \end{equation*}

The set \(A\) is really just the set of all \(k\)-subsets of the \((n-1)\)-set \(\{1, 2, 3, \ldots, n-1 \}\), so \(|A| = \binom{n-1}{k}\).

Any of the sets in \(B\) can be obtained by adjoining the element \(n\) to a \(k-1\) subset of the \((n-1)\)-set \(\{1, 2, 3, \ldots, n-1 \}\), so \(|B| = \binom{n-1}{k-1}\).

Substituting gives us the desired result.

(The second proof is algebraic in nature.)

Consider the sum \begin{equation*} \binom{n-1}{k} + \binom{n-1}{k-1}. \end{equation*}

Applying the formula we deduced in Section 7.1 we get \begin{gather*} \binom{n-1}{k} + \binom{n-1}{k-1}\\ = \frac{(n-1)!}{k! (n-1-k)!} + \frac{(n-1)!}{(k-1)! ((n-1)-(k-1))!}\\ = \frac{(n-1)!}{k! (n-k-1)!} + \frac{(n-1)!}{(k-1)! (n-k)!} \end{gather*}

A common denominator for these fractions is \(k!(n-k)!\). (We will have to multiply the top and bottom of the first fraction by \((n-k)\) and the top and bottom of the second fraction by \(k\).) \begin{gather*} = \frac{(n-k)(n-1)!}{k! (n-k) (n-k-1)!} + \frac{k (n-1)!}{k (k-1)! (n-k)!}\\ = \frac{(n-k)(n-1)!}{k! (n-k)!} + \frac{k (n-1)!}{k! (n-k)!}\\ = \frac{(n-k)(n-1)! + k (n-1)!}{k! (n-k)!}\\ = \frac{(n-k+k)(n-1)!}{k! (n-k)!}\\ = \frac{(n)(n-1)!}{k! (n-k)!}\\ = \frac{n!}{k! (n-k)!}. \end{gather*}

We recognize the final expression as the definition of \(\binom{n}{k}\), so we have proved that \begin{equation*} \binom{n-1}{k} + \binom{n-1}{k-1} = \binom{n}{k}. \end{equation*}

Using the formula for the value of a binomial coefficient we get \begin{equation*} k \cdot \binom{n}{k} = k \cdot \frac{n!}{k! (n-k)!}. \end{equation*}

We can do some cancellation to obtain \begin{equation*} k \cdot \binom{n}{k} = \frac{n!}{(k-1)! (n-k)!}. \end{equation*}

Finally we factor-out an \(n\) to obtain \begin{equation*} k \cdot \binom{n}{k} = n \cdot \frac{(n-1)!}{(k-1)! (n-k)!}, \end{equation*} since \((n-k)\) is the same thing as \(((n-1)-(k-1))\) we have \begin{equation*} k \cdot \binom{n}{k} = n \cdot \frac{(n-1)!}{(k-1)!((n-1)-(k-1))!} = n \cdot \binom{n-1}{k-1} \end{equation*}

Consider the collection of all subsets of size \(k\) taken from \(N = \{1, 2, 3, \ldots, n\}\) in which one of the elements has been marked to distinguish it from the others in some way.¹ For example, a committee of \(k\) individuals one of whom has been chosen as chairperson, is an example of the kind of entity we are discussing.

We can count this collection in two ways using the multiplication rule.

Firstly, we could select a \(k\)-subset in \(\binom{n}{k}\) ways and then from among the \(k\) elements of the subset we could select one to be marked. By this analysis there are \(\binom{n}{k} \cdot k\) elements in our collection.

Secondly, we could select an element from the \(n\)-set which will be the “marked” element of our subset, and then choose the additional \(k-1\) elements from the remaining \(n-1\) elements of the \(n\)-set. By this analysis there are \(n \cdot \binom{n-1}{k-1}\) elements in the collection we have been discussing.

Thus, \begin{equation*} k \cdot \binom{n}{k} = n \cdot \binom{n-1}{k-1} \end{equation*}

Substitute \(x=y=1\) in the binomial theorem.

The set of all subsets of \(N = \{1, 2, 3, \ldots, n\}\), which we denote by \({\mathcal P}(N)\), can be partitioned into \(n+1\) sets based on the sizes of the subsets, \begin{equation*} {\mathcal P}(N) = S_0 \cup S_1 \cup S_2 \cup \ldots \cup S_n, \end{equation*} where \(S_k = \{ S \suchthat S \subseteq N \; \land \; |S| = k \}\) for \(0 \leq k \leq n\). Since no subset of \(N\) can appear in two different parts of the partition (a subset's size is unique) and every subset of \(N\) appears in one of the parts of the partition (the sizes of subsets are all in the range from \(0\) to \(n\)). The addition principle tells us that \begin{equation*} |{\mathcal P}(N)| = |S_0| \;+\; |S_1| \;+\;\cup |S_2| \;+\; \ldots \;+\; |S_n|. \end{equation*}

We have previously proved that \(|{\mathcal P}(N)| = 2^n\) and we know that \(|S_k| = \binom{n}{k}\) so it follows that \begin{equation*} 2^n = \binom{n}{0} + \binom{n}{1} +\binom{n}{2} + \ldots + \binom{n}{n}. \end{equation*}