1 Statement of the rule

Pascal's rule is a recurrence relation for binomial coefficients. It states that, for integers \(n \ge 1\) and \(0 \le k \le n\), \[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}, \] with boundary conditions chosen so that the identity remains valid at the edges of the coefficient array. The rule captures a simple decomposition: to form a \(k\)-element subset of an \(n\)-element set, one may either include a fixed element or exclude it.

1.1 Binomial coefficient form

In binomial coefficient notation, the identity compares one coefficient with two neighboring coefficients from the preceding row. This relation is often written as \[ \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}. \] It applies for the range where the terms are defined in the usual combinatorial sense. The formula is one of the most basic recursive descriptions of combinations.

1.2 Pascal triangle form

In Pascal's triangle, each entry is obtained by adding the two entries directly above it. If the triangle is arranged so that row \(n\) contains the coefficients \(\binom{n}{0}, \binom{n}{1}, \dots, \binom{n}{n}\), then the recurrence exactly matches the construction of the triangle. The outer edges are filled with 1s, and all interior entries are sums of adjacent values from the previous row.

1.3 Boundary conditions

To make the rule work uniformly, the boundary values are taken as \[ \binom{n}{0}=\binom{n}{n}=1 \] for \(n \ge 0\), and \[ \binom{n}{k}=0 \] when \(k<0\) or \(k>n\). These conventions ensure that the recurrence remains consistent at the ends of each row and that the triangle has a simple and complete recursive structure.

2 Combinatorial interpretations

Pascal's rule has several natural counting interpretations. In each case, the key idea is to divide a collection of objects into two disjoint classes according to whether a chosen element or feature is present.

2.1 Counting subsets

One standard interpretation counts the number of \(k\)-element subsets of an \(n\)-element set. Fix one distinguished element. Every \(k\)-subset either contains that element or does not. The subsets containing it are counted by \(\binom{n-1}{k-1}\), while those excluding it are counted by \(\binom{n-1}{k}\). Their sum gives \(\binom{n}{k}\).

2.2 Choosing with or without a distinguished element

The same reasoning can be phrased as a choice process. If one is choosing \(k\) objects from \(n\), a particular object may be selected or left out. When it is selected, there remain \(k-1\) choices among the remaining \(n-1\) objects; when it is not selected, all \(k\) choices must come from those same \(n-1\) objects. This two-case split is the essence of the identity.

2.3 Lattice path interpretation

Pascal's rule also appears in counting lattice paths. The number of shortest paths from one grid point to another is often a binomial coefficient. A path to a given point can be classified by its last step, which is either one direction or the other. Counting paths by the final move leads directly to the same recurrence.

3 Proofs

Several proofs of Pascal's rule are standard. Some use algebraic manipulation, while others rely on counting arguments or induction.

3.1 Algebraic proof

An algebraic proof begins with the explicit formula for binomial coefficients and manipulates the expressions until the recurrence appears. This approach shows that Pascal's rule is not merely a counting coincidence but an identity built into the factorial form of combinations.

3.1.1 Proof using factorial definitions

Using \[ \binom{n}{k}=\frac{n!}{k!(n-k)!}, \] one computes \[ \binom{n-1}{k-1}+\binom{n-1}{k} = \frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}. \] With a common denominator, the terms combine to \[ \frac{(n-1)!k}{k!(n-k)!}+\frac{(n-1)!(n-k)}{k!(n-k)!} = \frac{(n-1)!(k+n-k)}{k!(n-k)!} = \frac{n!}{k!(n-k)!}, \] which is \(\binom{n}{k}\).

3.1.2 Proof using binomial identities

Another derivation uses standard relations among factorials or rational forms of binomial coefficients. By expressing neighboring coefficients in compatible forms and simplifying, one obtains the same recurrence. Such computations are often used to connect Pascal's rule with identities arising in algebra and generating functions.

3.2 Combinatorial proof

The most intuitive proof is combinatorial. Consider a fixed element in an \(n\)-element set and count all \(k\)-element subsets. Each subset either includes the fixed element or excludes it. The first class is counted by choosing the remaining \(k-1\) elements from the other \(n-1\) objects; the second by choosing all \(k\) elements from those \(n-1\) objects. Since the two classes are disjoint and exhaustive, their counts add to \(\binom{n}{k}\).

3.3 Proof by induction

Pascal's rule can also be established by induction on \(n\) or on \(k\), once the boundary conditions are set. The base cases are immediate from the definitions. Assuming the rule holds for earlier rows, one verifies that the formula remains true for the next row by substituting the inductive hypothesis into the relevant coefficients. Induction is especially useful when proving statements that depend on repeated application of the recurrence.

4 Connection to Pascal's triangle

Pascal's rule is the defining mechanism behind Pascal's triangle. The triangle is both a visual arrangement of binomial coefficients and a compact computational tool.

4.1 Construction of the triangle

Pascal's triangle begins with a top row containing 1. Each subsequent row starts and ends with 1, and every interior entry is the sum of the two entries above it. This rule generates rows such as \[ 1,\quad 1\ 1,\quad 1\ 2\ 1,\quad 1\ 3\ 3\ 1, \] and so on. The pattern reflects the recurrence exactly.

4.2 Row and entry indexing

A common indexing convention labels the \(n\)th row by the coefficients \(\binom{n}{k}\) for \(k=0,1,\dots,n\). Under this convention, row numbers increase downward, and positions within a row correspond to the parameter \(k\). Other indexing schemes shift the starting row, but the underlying recurrence remains unchanged.

4.3 Symmetry in the triangle

Pascal's triangle is symmetric because \[ \binom{n}{k}=\binom{n}{n-k}. \] This symmetry means each row reads the same from left to right and from right to left. The recurrence is compatible with this property, since the left and right sides of the triangle mirror one another.

5 Applications

Pascal's rule is used throughout combinatorics and related areas. Its recursive nature makes it useful for computation, proof, and modeling.

5.1 Computing binomial coefficients recursively

The identity provides a direct recursive method for generating binomial coefficients. Starting from the boundary values, one can build each new row from the previous one without evaluating factorials. This is efficient and conceptually simple, especially for constructing tables of coefficients by hand or by algorithm.

5.2 Binomial theorem

Pascal's rule underlies the coefficients in the binomial theorem. When expanding \[ (x+y)^n, \] the coefficients are \(\binom{n}{k}\). The recurrence explains how these coefficients evolve from one power to the next and helps establish the formula by induction. It also clarifies why the coefficients in expansions of powers of binomials match the rows of Pascal's triangle.

5.3 Probability and distributions

In probability, binomial coefficients appear in counting the number of ways a given number of successes can occur in repeated independent trials. Pascal's rule helps derive and simplify formulas for binomial distributions and related discrete models. It also supports recurrence relations for probabilities in processes with two outcomes.

5.4 Combinatorial identities

Many identities involving sums of binomial coefficients can be proved by repeated use of Pascal's rule. The recurrence often reduces a complicated expression to a simpler one by splitting terms into neighboring coefficients. It is also a common tool in proofs involving telescoping sums, generating functions, and counting arguments.

6 Generalizations

Pascal's rule has several extensions that appear in more advanced combinatorics and algebra. These generalizations preserve the basic idea of building coefficients from simpler neighboring values.

6.1 Multinomial coefficients

For multinomial coefficients, which count ways to divide \(n\) objects into more than two groups, analogues of Pascal's rule arise by fixing one object and distributing the rest among the remaining categories. The resulting recurrences are more elaborate but follow the same principle of splitting into cases according to whether a distinguished element is used.

6.2 \(q\)-analogues

In \(q\)-analogues, ordinary binomial coefficients are replaced by \(q\)-binomial coefficients, which encode additional algebraic or combinatorial structure. These quantities satisfy \(q\)-versions of Pascal-type recurrences in which the sum is modified by powers of \(q\). Such formulas play a role in partition theory and the combinatorics of finite vector spaces.

6.3 Higher-dimensional analogues

Higher-dimensional versions of Pascal-like recurrences appear in arrays and simplices of coefficients beyond the familiar triangle. In these settings, each entry is obtained from several neighboring entries rather than just two. The structure generalizes the same principle of recursive assembly from lower-dimensional data.

Pascal's rule is closely connected to several standard ideas in discrete mathematics. These topics provide broader context for the identity and its uses.

7.1 Pascal's identity

Pascal's identity is another name for the recurrence \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\). The term emphasizes the algebraic statement itself, independent of the geometric arrangement in Pascal's triangle.

7.2 Binomial coefficients

Binomial coefficients count combinations and appear in many algebraic and probabilistic formulas. Pascal's rule is one of their defining relations and one of the most useful ways to compute them.

7.3 Pascal's triangle

Pascal's triangle is the tabular arrangement of binomial coefficients. It visually displays the recurrence and reveals numerous patterns, including symmetry and the appearance of figurate numbers in selected diagonals.

7.4 Combinatorial proofs

Combinatorial proofs establish identities by counting the same set in two different ways. Pascal's rule is a classic example of this method and is often introduced as a model for more elaborate counting arguments.