Math Home
Combinatorics

Pascal's triangle is a useful tool for memorizing combinations and for multiplying polynomials. The triangle is generated as follows:

  1. The first row, or "Row \(0\)," of the triangle has a \(1\). It is centered at the top of the triangle.
  2. For each row that follows, branch every number in the previous row to the left and to the right. When two numbers collide they are added together.


Pascal's Triangle:
Row 0 1 Row 1 1 1 Row 2 1 2 1 Row 3 1 3 3 1 Row 4 1 4 6 4 1 Row 5 1 5 10 10 5 1 . . . . . .
The triangle is easy to generate using addition and allows one to quickly compute \({n \choose k}\) for small values of \(n\) based on the following fact:

Claim: The values in Row \(n\) of Pascal's triangle are \({n \choose 0}, {n \choose 1}, {n \choose 2}, \dots, {n \choose n}.\)

▼ Proof:
This result can be proved by induction.

Base case: The first row, Row 0, is \(1 = {0 \choose 0}.\) The second row is \(1, 1\) which is \({1 \choose 0}, {1 \choose 1}.\)

Inductive step: Suppose the claim is true for Row \(n.\) We need to show the claim is true for row \(n+1.\) By the rule that generates Pascal's triangle, the first and last value in Row \(n+1\) will be \(1.\) For \(2 \leq k \leq n,\) the \(k\)th value in Row \(n+1\) will be the sum of the \(k-1\)st value and the \(k\)th value in Row \(n.\)

For every \(n,\) \({n+1 \choose 0} = 1\) and \({n+1 \choose n+1} = 1,\) so the first and last value in Row \(n+1\) are accurate.

Let \(2 \leq k \leq n.\) Since the claim is true for Row \(n,\) the numbers in the \(k-1\)st value and \(k\)th value in Row \(n\) are \({n \choose k-1}\) and \({n \choose k}.\) Therefore, the \(k\)th value in Row \(n+1\) is \begin{align} {n \choose k-1} + {n \choose k} & = \frac{n!}{(k-1)!(n-k+1)!} + \frac{n!}{k!(n-k)!} \\ & = \frac{n!k}{k!(n-k+1)!} + \frac{n!(n-k+1)}{k!(n-k+1)!} \\ & = \frac{n!(k + n - k + 1)}{k!(n-k+1)!} \\ & = \frac{n!(n + 1)}{k!(n-k+1)!} \\ & = \frac{(n+1)!}{k!(n+1-k)!} \\ & = {n+1 \choose k} \\ \end{align} So, the claim is true for every position in Row \(n+1.\)

Example: In Row 4 above, the values of Pascal's triangle are \[ 1 = {4 \choose 0}, 4 = {4 \choose 1}, 6 = {4 \choose 2}, 4 = {4 \choose 3}, 1 = {4 \choose 4} \]
Find the next two rows of Pascal's triangle.