Proof of Pascals Theorem ${n \choose k} = {n-1 \choose k} + {n-1 \choose k-1}$ 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.
 A: 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)!}$
A: 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}$$ 
A: 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)$
