Pascal's Identity (Binomial Coefficient)

combinatorics

Definition

Pascal's Identity

For $n\ge 1$, adjacent binomial coefficients satisfy

$$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right).$$

Coefficients outside $0\le k\le n$ are interpreted as zero. The identity expresses each coefficient as the sum of the two coefficients immediately above it.

Combinatorial Derivation

Let $X$ be an $n$-element set and fix one distinguished element $x\in X$. Every $k$-element subset of $X$ belongs to exactly one of two disjoint classes:

1. It contains $x$, so its remaining $k-1$ elements are chosen from the other $n-1$ elements.
2. It excludes $x$, so all $k$ elements are chosen from the other $n-1$ elements.

These classes contain $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ and $\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$ subsets, respectively. Adding their sizes gives Pascal’s identity.

Example

Example

$$\left(\genfrac{}{}{0ex}{}{5}{2}\right)=\left(\genfrac{}{}{0ex}{}{4}{1}\right)+\left(\genfrac{}{}{0ex}{}{4}{2}\right)=4+6=10.$$