Today in class we saw one of the more fundamental properties of the binomial numbers, namely Pascal’s Relation, which is the following:

Pascal’s Relation. For every $n\geq 0$ and $0\leq k\leq n$, we have the equality

We saw how this relation could be used to quickly compute binomial numbers and fill out Pascal’s Triangle row by row. However, for the sake of time we only briefly talked about why the relation is true. Let’s take a look at a pair of different proofs.

An Algebraic Proof

We proved in class that $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ for every $n\geq 0$ and $0\leq k\leq n$. Let’s use this formula for each of the three binomial numbers appearing in Pascal’s Relation. Beginning with the left-hand side of the relation, we have
\binom{n}{k}+\binom{n}{k-1} &= \frac{n!}{k!(n-k)!}+\frac{n!}{(k-1)!(n-k+1)!}\\
&= \frac{n!}{k!(n-k)!}\cdot \frac{n-k+1}{n-k+1}+\frac{n!}{(k-1)!(n-k+1)!}\cdot \frac{k}{k}\\
&= \frac{(n!)(n-k+1)}{k!(n-k+1)!}+\frac{(n!)(k)}{k!(n-k+1)!}\\
&= \frac{(n!)(n-k+1+k)}{k!(n-k+1)!}\\
&= \frac{(n!)(n+1)}{k!(n+1-k)!}\\
&= \frac{(n+1)!}{k!(n+1-k)!}\\
&= \binom{n+1}{k}.

Observe that nothing sneaky happened. We simply put the two fractions over a common denominator, combined them, and simplified. This certainly proves the relation is true, but it doesn’t give much insight into why it is true.

A Combinatorial Proof

We claim both sides of the relation count the same thing, namely the number of subsets of size $k$ of a set of size $n+1$. In fact, that is exactly our definition of $\binom{n+1}{k}$. The question, then, is why does the right-hand side also count that number? To see how it does, imagine choosing one element from the set of $n+1$ elements, say element $a$. Now consider the subsets of size $k$. There are exactly two types: those that contain $a$, and those that do not. How many subsets are there of the first type? A subset of size $k$ that contains $a$ consists of the element $a$ and exactly $k-1$ of the other $n$ elements. There are thus $\binom{n}{k-1}$ of these type of subsets. A subset of size $k$ that does not contain $a$ consists of exactly $k$ of the other $n$ elements (that aren’t $a$). There are therefore exactly $\binom{n}{k}$ of these subsets. Since every subset of size $k$ of the original set of $n+1$ elements is exactly one of these two types of subsets, we’ve thus proven that the number of such subsets is $\binom{n}{k-1}+\binom{n}{k}$. We’ve counted the same thing in two different ways, and thus deduced that $\binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k}$.

This proof has the advantage of making the relation arguably “more intuitive” and easier to re-derive. It has the disadvantage of being more long winded.

Both proofs are equally valid, and both have their advantages and disadvantages. Fortunately for us, there is no need to pick a favorite. We can appreciate them both for what they are.