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

\[

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

\]

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

\begin{align*}

\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}.

\end{align*}

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.

Chad CollinsSeptember 24, 2016 at 9:04 amHello,

I’m not sure who will see this, but I figured I’d try out the feature anyway. I’m having some trouble with the combinatorial proof, specifically where it says:

“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.”

I’m having trouble understanding why $\binom{n}{k-1}$ describes the subsets of size $k$ that do contain $a$ as well as why we have $n$ instead of $n+1$ like the original set. Is it because we “removed” $a$?

RobSeptember 24, 2016 at 11:06 amGreat question! At that point in the proof, we are trying to count the number of subsets of size $k$ of a set of $n+1$ elements, with the additional requirement that the subset contain the special element $a$. So, each such subset contains $a$ and exactly $k-1$ other elements. How many choices are there for those $k-1$ other elements? They can be any of the elements from the original set (of $n+1$ elements)

except$a$. There are therefore $n$ elements to choose from, and so we have $\binom{n}{k-1}$ possible ways to choose those remaining $k-1$ elements.For example, suppose $n=4$ and the original set of elements is labeled $\{a,b,c,d\}$. Let’s look at all of the subsets of size 2. There are two types: those that contain $a$, and those that do not. How many are there that contain $a$? Each such subset has two elements, one of which is $a$ and one of which is either $b, c$, or $d$. So there are $\binom{3}{1}$ such subsets, namely $\{a,b\}, \{a,c\}$, and $\{a,d\}$.

In this same example, how many subsets of size 2 do

notcontain $a$? Such subsets must contain two elements, neither of which is $a$. There is therefore only $\binom{3}{2}$ of them, namely the subsets $\{b,c\},\{b,d\}$ and $\{c,d\}$.Every subset of size 2 of the original set $\{a,b,c,d\}$ has now been accounted for. This is an illustration of the equality $\binom{4}{2}=\binom{3}{1}+\binom{3}{2}$.

Chad CollinsSeptember 24, 2016 at 4:12 pmThank you Professor!