3
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – James Pirlman Jul 28 '13 at 4:20
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.