# Why does Pascal's Triangle give the Binomial Coefficients?

An exercise in chapter 2 of Spivak's Calculus (4th ed.) talks about how Pascal's triangle gives the binomial coefficients. It explains this by saying that the relation $\binom{n+1}{k} = \binom{n}{k-1}+\binom{n}{k}$. I'm having trouble seeing how this equation gives rise to Pascal's triangle, so any explanation of what's really going on would be helpful, thanks.

If $(n,k)$ is the $k$th entry of the $n$th row of Pascal's triangle, then we have the following equation from the way Pascal's triangle is built:

$$(n+1,k)=(n,k-1)+(n,k)$$

Notice the similarity with the binomial coefficient identity you mention. Now, since $(n,1)=(n,n)=1$, and since $\binom{n}{1}=\binom{n}{n}=1$, by induction it follows that $(n,k)=\binom{n}{k}$.

Explicitly, if $(n,k)=\binom{n}{k}$ for all $k=1,\ldots,n$, then we have

$$(n+1,k)=(n,k-1)+(n,k)=\binom{n}{k-1}+\binom{n}{k}=\binom{n+1}{k}$$

for all $k=1,\ldots,n$, and by definition, we already have $(n+1,n+1)=1=\binom{n+1}{n+1}$

• Great answer, thanks. One question though: in Spivak it defines $\binom{n}{k}$ as the $(k+1)$st number in the $(n+1)$st row, so I'm assuming he counts the top row as row 0 so that it gives $\binom{0}{0} = 1$. Is this the correct reasoning, or is there something else behind this? I don't think it changes your proof much, anyhow. – James Pirlman Jul 28 '13 at 4:20

I was also wondering about the intuition behind this connection. We can develop intuition for what's going on in a few steps. The first is to realize that $\binom{n}{0}$ = $\binom{n}{n}$ = 1 (note that there is a mistake in Jared's answer, $\binom{n}{1}$ = n). This is because there is only one way to choose no objects out of a set of n, and also one way to choose all of them.

From here, we can apply the recursive rule listed in the original post. We have that $\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$. I do some slight re-indexing so that we can think of $\binom{n}{k}$ as the element that we are currently adding to the triangle. $\binom{n}{k}$ is the number of ways that we can choose a subset of size k out of a set of size n. We can think of these subsets in terms of smaller subsets from a set of size n-1. Consider the nth element that is included in our set of size n, but not in our set of size n-1. This element is either included or not included in each of our $\binom{n}{k}$ subsets. For the subsets where it is included, there is a one to one correspondence with a $\binom{n-1}{k-1}$ subset (just remove the nth element). For the subsets where it is not included, there is a one to one correspondence with a $\binom{n-1}{k}$ subset (it is the same subset). Thus the number of $\binom{n}{k}$ subsets is equal to the number of $\binom{n-1}{k-1}$ subsets plus the number of $\binom{n-1}{k}$ subsets. This gives us $\binom{n}{k}$ = $\binom{n-1}{k-1}$ + $\binom{n-1}{k}$.

I also found it instructive to look at Pascal's triangle with each line written out as a polynomial in x and y (the Binomial coefficient perspective). See page 2 of https://www.mathcamp.org/2017/pascal.pdf. From this perspective, we can think of each term in the expansion of $(x + y)^n$ as representing one subset of a set of size n, where the ith x indicates that the ith object is excluded, and the ith y represents that the ith object is included. For example, $$(x + y)^3 = (x + y)(x + y)(x + y) \\ = (xx + xy + yx + yy)(x + y) \\ = xxx + xyx + yxx + yyx + xxy + xyy + yxy + yyy \\ = 1x^3y^0 + 3x^2y^1 + 3x^1y^2 + 1x^0y^3$$

Collecting terms with like powers, we can see that the binomial coefficients for each power of y reflect the number of ways we can select that power of objects out of a set of size n. This explains the connection between binomial coefficients and $\binom{n}{k}$.