Pascal's rule

In mathematics, Pascal's rule (or Pascal's formula) is a combinatorial identity about binomial coefficients. It states that for positive natural numbers n and k, $${\displaystyle {n-1 \choose k}+{n-1 \choose k-1}={n \choose k},}$$ where ${\displaystyle {\tbinom {n}{k}}}$ is a binomial coefficient; one interpretation of 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] since, if n < k the value of the binomial coefficient is zero and the identity remains valid.

Pascal's rule can also be viewed as a statement that the formula $${\displaystyle {\frac {(x+y)!}{x!y!}}={x+y \choose x}={x+y \choose y}}$$ solves the linear two-dimensional difference equation $${\displaystyle N_{x,y}=N_{x-1,y}+N_{x,y-1},\quad N_{0,y}=N_{x,0}=1}$$ over the natural numbers. Thus, Pascal's rule is also a statement about a formula for the numbers appearing in Pascal's triangle.

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