Proof of the number of k-element subsets by induction

Proof

For a set $X$ and a natural number $k$, let $C(X, k)$ be the set of $k$-combinations of $X$, the subsets with exactly $k$ elements. We argue by induction on $n = |X|$ that $|C(X, k)| = \binom{n}{k}$ for every $k$.

1. Let $n = 0$. Then $X = \varnothing$, and its only subset $\varnothing$ has $0$ elements.
2. So $|C(X, 0)| = 1 = \binom{0}{0}$ and $|C(X, k+1)| = 0 = \binom{0}{k+1}$, by the definition of the binomial coefficient.
3. Suppose the claim holds for all sets with $n$ elements. Let $|X| = n + 1$, with a bijection $f : \set{1, \dots, n+1} \to X$.
4. Put $x = f(n+1)$ and $X' = X \setminus \set{x}$. The restriction of $f$ to $\set{1, \dots, n}$ is a bijection onto $X'$, so $|X'| = n$.
5. Only $\varnothing$ has $0$ elements, so $|C(X, 0)| = 1 = \binom{n+1}{0}$.
6. Now fix $k \ge 0$. Split $C(X, k+1)$ into $C_{\mathrm{out}}$, the sets that omit $x$, and $C_{\mathrm{in}}$, the sets that contain $x$. These parts are disjoint.
7. The sets in $C_{\mathrm{out}}$ are exactly the $(k+1)$-element subsets of $X'$. By the induction hypothesis, $|C_{\mathrm{out}}| = \binom{n}{k+1}$.
8. For $S \in C_{\mathrm{in}}$, the set $S \setminus \set{x}$ is a subset of $X'$. By the complement principle in $S$, it has $(k+1) - 1 = k$ elements.
9. For $T \in C(X', k)$, the sets $T$ and $\set{x}$ are disjoint, since $x \notin X'$. By the rule of sum, $T \cup \set{x}$ has $k + 1$ elements, so it lies in $C_{\mathrm{in}}$.
10. The maps $S \mapsto S \setminus \set{x}$ and $T \mapsto T \cup \set{x}$ are mutually inverse. So they are bijections between $C_{\mathrm{in}}$ and $C(X', k)$.
11. By the induction hypothesis, $C(X', k)$ has $\binom{n}{k}$ elements. Composing a numbering of it with $T \mapsto T \cup \set{x}$ numbers $C_{\mathrm{in}}$. So $|C_{\mathrm{in}}| = \binom{n}{k}$, as in the bijection principle.
12. By the rule of sum, $|C(X, k+1)| = \binom{n}{k} + \binom{n}{k+1}$.
13. By Pascal's rule, this equals $\binom{n+1}{k+1}$. Together with step 5, the claim holds for all $k$, and the induction is complete.