Pascal's rule

Pascal's rule states that each interior binomial coefficient equals the sum of the two adjacent coefficients in the preceding row of Pascal's triangle. In symbols, \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\).

Binomial coefficient: A binomial coefficient counts ways to choose a fixed-size subset and appears as a coefficient in a binomial expansion. Pascal's rule is a recurrence relating binomial coefficients with neighboring indices.
Pascal identity: The recurrence \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\) for binomial coefficients. This standard algebraic form states Pascal's rule independently of the triangle picture.
Dynamic programming: An algorithmic approach that solves problems by storing and reusing solutions to overlapping subproblems. Pascal's rule computes a table of binomial coefficients without repeated factorial calculations.
Vandermonde's identity: An identity expressing a binomial coefficient of a sum as a sum of products of binomial coefficients. It relates coefficients across different rows rather than just neighboring entries.
Combinatorial proof: A proof that establishes an identity by interpreting both sides as counts of the same set of objects. Split subsets according to whether they contain one distinguished element to derive the rule.
Factorial: For a nonnegative integer, the product of all positive integers up to that integer, with zero factorial equal to one. Factorial formulas let the recurrence be checked directly from the definition of binomial coefficients.
Binomial distribution: A probability distribution for the number of successes in a fixed number of independent trials with equal success probability. Its probability formula contains coefficients readily computed by the recurrence.
Multinomial coefficient: A coefficient counting partitions of a set into several specified sizes, generalizing binomial coefficients. Its recurrence extends Pascal-style addition to choices among more than two groups.
Binomial theorem: The theorem expressing powers of a sum as a sum of terms weighted by binomial coefficients. Pascal's recurrence generates the coefficients used in successive binomial expansions.
Subset: A set formed from some or all elements of another set. The counting proof partitions subsets by the presence of a chosen element.

Linked from 4 pages

Hockey-stick identityRelated: Repeatedly applying this recurrence makes adjacent terms cancel in a telescoping proof.