# Solution

Pascal's triangle can be constructed in the following way. First, we write a bunch of ones along the left and right edges, and then below each pair of adjacent numbers we write their sum.

As another way to construct Pascal's triangle -- it is well known that the $n^{th}$ row (where the top row corresponds to $n=0$) yields the coefficients to the terms resulting from expanding $(x+y)^n$.

The Binomial Theorem gives a way to produce these coefficients, stating that
$$(x+y)^n = x^n + {}_nC_1 x^{n-1} y + {}_nC_2 x^{n-2} y^2 + {}_nC_3 x^{n-3} y^3 + \cdots + {}_nC_{n-1} x y^{n-1} + y^n$$
where ${}_nC_k$ counts the number of ways to choose $k$ objects from a group of $n$ objects, which is given by
$${}_nC_k = \frac{n!}{k! (n-k)!}$$
How do we know the two techniques described for constructing Pascal's triangle yield the same numbers?

Consider the numbers seen in the triangle constructed by looking at the coefficients seen in the expansion of $(x+y)^n$. These are given by the binomial theorem, and all take the form ${}_nC_k$ for some appropriate non-negative integers $n$ and $k$.

Suppose we look at one such number, ${}_nC_k$. This number lies on the $n^{th}$ row. If it lies on an end of this row, then either $k=0$ or $k=n$. Note ${}_nC_0 = {}_nC_n = 1$. This explains the ones seen on the left and right sides of Pascal's triangle.

Now suppose ${}_nC_k$ is not on the end of a row. Then ${}_nC_{k+1}$ would be the number to its right. Likewise, ${}_{n+1}C_{k+1}$ would be the number on the next row, directly below ${}_nC_k$ and ${}_nC_{k+1}$.

As such, we seek to argue that ${}_nC_k + {}_nC_{k+1} = {}_{n+1}C_{k+1}$, as this will establish that the "adding-the-two-above" technique for constructing Pascal's triangle yields the same numbers as the triangle constructed from finding coefficients of $(x+y)^n$ expanded.

We proceed directly...

$$\begin{array}{rcl} {}_nC_k + {}_nC_{k+1} &=& \frac{n!}{k!(n-k)!} + \frac{n!}{(k+1)!(n-k-1)!}\\\\\\ &=& \frac{n!}{k!(n-k)!} \cdot \frac{(k+1)}{(k+1)} + \frac{n!}{(k+1)!(n-k-1)!} \cdot \frac{(n-k)}{(n-k)}\\\\\\ &=& \frac{k \cdot n! + n! + n \cdot n! - k \cdot n!}{(k+1)! (n-k)!}\\\\\\ &=& \frac{(n+1) n!}{(k+1)!(n-k)!} \quad = \quad {}_{n+1}C_{k+1} \end{array}$$