Pascal's rule (source code)

= Pascal's rule
{c}
{title2=$\binom nk=\binom{n-1}k+\binom{n-1}{k-1}$}
{wiki}

= Pascal's identity
{c}
{synonym}

Pascal's identity is
$$
\binom nk=\binom{n-1}k+\binom{n-1}{k-1}.
$$

For an <integer> $n\geq1$ and any <integer> $k$, <Pascal's rule> holds with the convention $\binom nk=0$ outside $0\leq k\leq n$. The boundary values are $\binom n0=\binom nn=1$, including $\binom00=1$. Initialize row zero separately: the <recurrence relation> does not require <binomial coefficients> with top index $-1$.<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]{ref}

\b[Proof by a marked element.] Count the $k$-element <subsets> of $\{1,\ldots,n\}$, marking the element $n$ as special. Those omitting $n$ are exactly the $k$-element <subsets> of $\{1,\ldots,n-1\}$. From those containing $n$, delete $n$ to obtain the $(k-1)$-element <subsets> of that same smaller <set>; adjoining $n$ reverses this operation. The <rule of sum> adds these two disjoint counts. The proof includes $k=0$ and $k=n$ because the impossible class contributes zero.

For an original worked instance, choose three labels from $\{1,2,3,4,5,6,7\}$ and mark $7$. Omitting it gives $\binom63=20$ selections. Including it leaves two labels to choose from the other six, giving $\binom62=15$. Therefore $\binom73=20+15=35$. Under the <bijection> with <north-east lattice paths> to $(4,3)$, 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>.