For an integer and any integer , Pascal's rule holds with the convention outside . The boundary values are , including . Initialize row zero separately: the recurrence relation does not require binomial coefficients with top index .[ref]
Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin. §1.2, Recurrence relation for binomial coefficients and Pascal's Triangle: edge values and the two-parent rule
Proof by a marked element. Count the -element subsets of , marking the element as special. Those omitting are exactly the -element subsets of . From those containing , delete to obtain the -element subsets of that same smaller set; adjoining reverses this operation. The rule of sum adds these two disjoint counts. The proof includes and because the impossible class contributes zero.
For an original worked instance, choose three labels from and mark . Omitting it gives selections. Including it leaves two labels to choose from the other six, giving . Therefore . Under the bijection with north-east lattice paths to , membership of position seven says whether the final step is north: the marked-element split becomes the last-step split.
This makes Pascal's rule useful beyond an algebraic identity. A counting problem may have an obvious yes-or-no decision even when its factorial formula is obscure; splitting at that decision exposes a recurrence relation. When the smaller counts are shared between many cases, dynamic programming reuses them. The beauty of Pascal's triangle is that one local addition rule simultaneously organizes subsets, binary strings, north-east lattice paths, and the binomial theorem.
Pascal's rule, also known as Pascal's triangle property, refers to a specific combinatorial identity related to binomial coefficients.
New to topics? Read the docs here!