All notes
Combinatorics

Pascal's rule

Wikipedia.

Definition

$$ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \quad (1\le k \le n) $$

Proof

Combinatorial proof

$\binom{n}{k}$ is the number of ways of picking a subset with $k$ elements ($k$-set) from a set with $n$ elements ($n$-set). For an item "X" in $n$-set, there are two cases:

Algebraic proof

$$ \binom{n-1}{k-1} + \binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-k)!} + \frac{(n-1)!}{k!(n-1-k)!} $$ $$ = \frac{(n-1)!k}{k!(n-k)!} + \frac{(n-1)!(n-k)}{k!(n-k)!} $$ $$ = \frac{(n-1)!k + (n-1)!(n-k)}{k!(n-k)!} $$ $$ = \frac{n!}{k!(n-k)!} $$