Pascal's rule

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. The binomial coefficients are the numbers that appear in Pascal's triangle. Pascal's rule states that for positive integers n and k, $${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}$$ where ${\displaystyle {\tbinom {n}{k}}}$ is the binomial coefficient, namely the coefficient of the x^k term in the expansion of (1 + x)ⁿ. There is no restriction on the relative sizes of n and k;^[1] in particular, the above identity remains valid when n < k since ${\displaystyle {\tbinom {n}{k}}=0}$ whenever n < k.

Together with the boundary conditions ${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$ for all nonnegative integers n, Pascal's rule determines that $${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}},}$$ for all integers 0 ≤ k ≤ n. In this sense, Pascal's rule is the recurrence relation that defines the binomial coefficients.

Pascal's rule can also be generalized to apply to multinomial coefficients.