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