A Tale of Two Proofs

///A Tale of Two Proofs

A Tale of Two Proofs

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.

By |2017-01-01T15:40:08+00:00September 23rd, 2016|Categories: Courses, Math 341|Tags: |3 Comments

3 Comments

  1. Chad Collins September 24, 2016 at 9:04 am - Reply

    Hello,

    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$?

    • Rob September 24, 2016 at 11:06 am - Reply

      Great 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 not contain $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}$.

  2. Chad Collins September 24, 2016 at 4:12 pm - Reply

    Thank you Professor!

Leave A Comment Cancel reply

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.

This Is A Custom Widget

This Sliding Bar can be switched on or off in theme options, and can take any widget you throw at it or even fill it with your custom HTML Code. Its perfect for grabbing the attention of your viewers. Choose between 1, 2, 3 or 4 columns, set the background color, widget divider color, activate transparency, a top border or fully disable it on desktop and mobile.