Theorem 1.6

#Theorem

Let $n$ and $k$ be positive integers with $n \geq k$ . Then $(\binom{n + 1}{k}) = (\binom{n}{k - 1}) + (\binom{n}{k})$

Proof:

Let $T$ be a set containing $n + 1$ elements. Let $a \in T$ and $S = T ∖ {a}$
There are $(\binom{n + 1}{k})$ subsets of $T$ containing $k$ elements.

A subset of $T$ with $k$ elements either contains $a$ together with $k - 1$ elements of $S$ , or contains $k$ elements of $S$ and does not contain $a$ .

So there are $(\binom{n}{k - 1})$ subsets of $T$ with $k$ elements that contain $a$ , and $(\binom{n}{k})$ subsets of $T$ with $k$ elements that do not contain $a$
Therefore, $(\binom{n + 1}{k}) = (\binom{n}{k - 1}) + (\binom{n}{k})$