Counting Principles - Key Proof

Pascal's Identity is one of the most elegant and useful results in combinatorics, providing both a recursive formula for computing binomial coefficients and the foundation for Pascal's triangle.

DefinitionPascal's Identity

For integers $n$ and $r$ with $1 \leq r \leq n$ , $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

with boundary conditions $\binom{n}{0} = \binom{n}{n} = 1$ for all $n \geq 0$ .

Proof (Combinatorial):

We give a bijective proof by counting the same set in two different ways.

Let $S$ be a set with $n$ elements, and fix a particular element $x \in S$ . We wish to count the number of $r$ -element subsets of $S$ , which is $\binom{n}{r}$ .

We partition the $r$ -element subsets into two disjoint classes:

Those that contain $x$
Those that do not contain $x$

Class 1: If a subset contains $x$ , we need to choose the remaining $r-1$ elements from the $n-1$ elements in $S \setminus \{x\}$ . The number of such subsets is $\binom{n-1}{r-1}$ .

Class 2: If a subset does not contain $x$ , we need to choose all $r$ elements from the $n-1$ elements in $S \setminus \{x\}$ . The number of such subsets is $\binom{n-1}{r}$ .

These two classes are disjoint and exhaustive (every $r$ -element subset either contains $x$ or doesn't), so by the addition principle: $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

This completes the combinatorial proof. $\square$

Proof (Algebraic):

We can also prove Pascal's identity algebraically using the factorial formula for binomial coefficients: $\binom{n-1}{r-1} + \binom{n-1}{r} = \frac{(n-1)!}{(r-1)!(n-r)!} + \frac{(n-1)!}{r!(n-1-r)!}$

Finding a common denominator: $= \frac{r \cdot (n-1)!}{r!(n-r)!} + \frac{(n-r) \cdot (n-1)!}{r!(n-r)!}$

$= \frac{r \cdot (n-1)! + (n-r) \cdot (n-1)!}{r!(n-r)!}$

$= \frac{(n-1)![r + (n-r)]}{r!(n-r)!}$

$= \frac{n \cdot (n-1)!}{r!(n-r)!} = \frac{n!}{r!(n-r)!} = \binom{n}{r}$

This completes the algebraic proof. $\square$

ExamplePascal's Triangle

Pascal's identity generates Pascal's triangle, where each entry is the sum of the two entries above it:

\begin{array}{ccccccc} & & & 1 & & & \\ & & 1 & & 1 & & \\ & 1 & & 2 & & 1 & \\ 1 & & 3 & & 3 & & 1 \end{array}

The $n$ -th row (starting from row 0) contains the binomial coefficients $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ .

Remark

Pascal's identity is computationally significant because it allows us to compute binomial coefficients recursively without directly computing factorials, which can overflow for large values. The identity also has a probabilistic interpretation: if we have $n$ independent trials, the probability of exactly $r$ successes can be expressed in terms of the probabilities for $n-1$ trials by conditioning on whether the $n$ -th trial succeeds. This connects combinatorics to probability theory in a fundamental way.