Proof of Pascals Theorem ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$

Question

Is the ensuing proof correct. If it is 'correct' could it be improved or simplfied?

Let $A$ be the union of the sets of subsets of $[n-1]$ with length $k$ and length $k-1$. Let $B$ be the set of subsets of $[n]$ with length $k$.

Define a bijection $f: A \longrightarrow B$ given by

$$f(X) = \begin{cases} X, & \text{if |X| = k} \\ X \cup \{n\}, & \text{if |X| = k-1} \end{cases} $$

To prove $f$ is bijective we will show it is both injective and surjective.

Consider distinct $x,y \in A$ applying $f$ to $x$ and $y$ will result in either $x$, $y$ or $x \cup \{n\}$, $y \cup \{n\}$ respectively. Since x and y are distinct $x \cup \{n\} \neq y \cup \{n\}$, it is also clear $x \neq y \cup \{n\}$ and $y \neq x \cup \{n\}$. We proven by contrapositive that $f$ is injective.

consider $x \in B$ either $x$ contains n or not. If $x$ contains $n$ simply remove $n$ and $x$ becomes a subsets of length $k-1$, since A contains all subsets of [n] with length $k-1$ there is always an element that can map to $x$. If $x$ contains $n$ then it is mapped by itself. Therefore $f$ is surjective.

We have shown a bijection from $A$ to $B$ hence $|A| = |B|$. Since $|A| = {n \choose k}$ and $|B| = {n-1 \choose k} + {n-1 \choose k-1}$ we have proven Pascals Theorem.

Answer 1

Since you are open to a simpler proof, why not just use the Combinatorial expansions?

${n-1 \choose k} + {n-1 \choose k-1} = \frac{(n-1)!}{k!(n-k-1)!} + \frac{(n-1)!}{(k-1)!(n-k)!} = \frac{(n-1)!}{(n-k-1)!(k-1)!} (\frac{1}{k} + \frac{1}{n-k}) = \frac{(n-1)!}{(n-k-1)!(k-1)!} (\frac{n}{k(n-k)}) = \frac{n(n-1)!}{(k(k-1)!)((n-k)(n-k-1)!)} = \frac{n!}{k!(n-k)!}$

Answer 2

Another option is to use a story proof, maybe not as strong as a mathematical proof but gives a better intuition why this is true.

Consider n people with one designated the leader of the group. If you want to form a committee of $k$ people out of $n$ you have two options:

• the leader must be part of the group. That means that you have to pick $k-1$ people from the $n-1$, hence $\binom{n-1}{k-1}$.
• the leader must not be part of the group. That means you will have to pick $k$ people from the $n-1$, hence $\binom{n-1}{k}$.

If you sum up the above binomial coeficients you have the ways to pick $k$ people out of $n$:

$$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$

Answer 3

The OP's proof is correct. Here the arguments are expanded into the excruciating details.

---

Here we derive Pascal's rule using elementary set theory
(the definition of binomial coefficient is not needed).

First some preliminaries...

If $S$ is a set then $\mathcal P(S)$ denotes the power set of $S$.

If $S$ is a set and $r$ is a natural number define

$\tag 1 \mathcal P_r(S) = \{x \in \mathcal P(S) \mid |x| = r \text{ (i.e. } x \text{ has } r \text{ elements)}\}$

The set $\{1,2,\dots,m\}$ is denoted by $\overline m$.

Continuing...

The number of $r\text{-combinations}$ from a given set $S$ of $n$ elements is often denoted in elementary combinatorics texts by $\displaystyle C(n,r)$.
(see Combination)

Using set theory one shows that the number $C(n,r)$ is the number of elements in the set $\mathcal P_r(\overline n)$.

We define two subsets $A_{+n}$ and $A_{-n}$ of $\mathcal P_r(\overline n)$:

$\tag 2 A_{+n} = \{x \in \mathcal P_r(\overline n) \mid n \in x\}, \quad \quad \quad A_{-n} = \{x \in \mathcal P_r(\overline n) \mid n \notin x\}$

It is immediate that this gives a two block partition of $\mathcal P_r(\overline n)$ and therefore

$\tag 3 |\mathcal P_r(\overline n)| = |A_{+n}| + |A_{-n}|$

The identity transformation is a natural bijection,

$\tag 4 {\displaystyle \iota : \mathcal P_r(\overline {n-1}) \equiv A_{-n}}$

The auxiliary mapping $\alpha$ defined on $P_{r-1}(\overline {n-1})$ by

$\tag 5 x \mapsto x \cup \{n\}$

is readily seen to be an injection with image equal $A_{+n}$.

Putting $\text{(3) thru (5)}$ together, we see that

$\tag 6 |\mathcal P_r(\overline n)| = |\mathcal P_{r-1}(\overline {n-1}))| + |\mathcal P_r(\overline {n-1})|$

and can therefore write as true

$\tag {7} C(n,r) = C(n-1,r-1) + C(n-1,r)$