Pascal's Identity (Binomial Coefficient)

combinatorics

Definition

Pascal's Identity

For , adjacent binomial coefficients satisfy

Coefficients outside are interpreted as zero. The identity expresses each coefficient as the sum of the two coefficients immediately above it.

Combinatorial Derivation

Let be an -element set and fix one distinguished element . Every -element subset of belongs to exactly one of two disjoint classes:

1. It contains , so its remaining elements are chosen from the other elements.
2. It excludes , so all elements are chosen from the other elements.

These classes contain and subsets, respectively. Adding their sizes gives Pascal’s identity.

Example

Example