All notes
Combinatorics

# Pascal's rule

## 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:

• "X" in $k$-subset. Then we only need to pick $k-1$ from $n-1$, which is $\binom{n-1}{k-1}$.
• "X" not in $k$-subset. Then we need to pick $k$ from $n-1$, which is $\binom{n-1}{k}$.

### 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)!}$$