# Pascal's Rule

## Contents

## Theorem

Let $\dbinom n k$ be a binomial coefficient.

For positive integers $n, k$ with $1 \le k \le n$:

- $\dbinom n {k-1} + \dbinom n k = \dbinom {n+1} k$

This is also valid for the real number definition:

- $\forall r \in \R, k \in \Z: \dbinom r {k-1} + \dbinom r k = \dbinom {r+1} k$

Thus the binomial coefficients can be defined using the following recurrence relation:

- $\dbinom n k = \begin{cases} 1 & : k = 0 \\ 0 & : k > n \\ \dbinom{n-1}{k-1} + \dbinom{n-1}{k} & : \text{otherwise} \end{cases}$

## Direct Proof

Let $n, k \in \N$ with $1 \le k \le n$.

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \binom n k + \binom n {k-1}\) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{n!}{k! \ \left({n - k}\right)!} + \frac{n!}{\left({k - 1}\right)! \ \left({n - \left({k - 1}\right)}\right)!}\) | \(\displaystyle \) | \(\displaystyle \) | Definition of Binomial Coefficient | ||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{n! \ \left({n - \left({k - 1}\right)}\right)} {k! \ \left({n - k}\right)! \ \left({n - \left({k - 1}\right)}\right)} + \frac{n! \ k}{\left({k - 1}\right)! \ \left({n - \left({k - 1}\right)}\right)! \ k}\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{n! \ \left({n - k + 1}\right)} {k! \ \left({n - k + 1}\right)!} + \frac {n! \ k}{k! \ \left({n - k + 1}\right)!}\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{n! \ \left({n - k + 1}\right) + n! \ k} {k! \ \left({n - k + 1}\right)!}\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{n! \ \left({n - k + 1 + k}\right)} {k! \ \left({n - k + 1}\right)!}\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{n! \ \left({n + 1}\right)}{k! \ \left({n - k + 1}\right)!}\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \frac{\left({n + 1}\right)!} {k! \ \left({n + 1 - k}\right)!}\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \binom {n+1} k\) | \(\displaystyle \) | \(\displaystyle \) |

$\blacksquare$

## Combinatorial Proof

Suppose you were a member of a club with $n + 1$ members (including you).

Suppose it were time to elect a committee of $k$ members from that club.

From Cardinality of Set of Subsets, there are $\displaystyle \binom {n+1} k$ ways to select the members to form this committee.

Now, you yourself may or may not be elected a member of this committee.

Suppose that, after the election, you are not a member of this committee.

Then, from Cardinality of Set of Subsets, there are $\displaystyle \binom n k$ ways to select the members to form such a committee.

Now suppose you *are* a member of the committee. Apart from you, there are $k-1$ such members.

Again, from Cardinality of Set of Subsets, there are $\displaystyle \binom n {k-1}$ ways of selecting the *other* $k-1$ members so as to form such a committee.

In total, then, there are $\displaystyle \binom n k + \binom n {k-1}$ possible committees.

Hence the result.

$\blacksquare$

## Proof for Real Numbers

From Factors of Binomial Coefficients:

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \left({r + 1}\right) \binom r {k - 1} + \left({r + 1}\right) \binom r k\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle k \binom {r + 1} k + \left({r + 1 - k}\right) \binom {r + 1} k\) | \(\displaystyle \) | \(\displaystyle \) | |||

\(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(\displaystyle \) | \(=\) | \(\displaystyle \) | \(\) | \(\displaystyle \) | \(\displaystyle \left({r + 1}\right) \binom {r + 1} k\) | \(\displaystyle \) | \(\displaystyle \) |

Dividing by $\left({r + 1}\right)$ yields the solution.

$\blacksquare$

## Also see

## Source of Name

This entry was named for Blaise Pascal.

## Sources

- Milton Abramowitz and Irene Stegun:
*Handbook of Mathematical Functions*(1964)... (previous)... (next): $3.1.4$: Binomial Coefficients - Seth Warner:
*Modern Algebra*(1965)... (previous)... (next): $\S 19$: Theorem $19.10$ - Murray R. Spiegel:
*Mathematical Handbook of Formulas and Tables*(1968)... (previous)... (next): $\S 3$: The Binomial Formula and Binomial Coefficients: $3.6$ - George E. Andrews:
*Number Theory*(1971)... (previous)... (next): $\S 3.1$: Exercise $3$ - Robert H. Kasriel:
*Undergraduate Topology*(1971)... (previous)... (next): $\S 1.18$: Sequences Defined Inductively: Exercise $3 \ \text{(c)}$ - P.M. Cohn:
*Algebra Volume 1*(2nd ed., 1982)... (previous)... (next): $\S 2.1$: The integers: Exercise $12$ - Larry C. Andrews:
*Special Functions of Mathematics for Engineers*(1992)... (previous)... (next): $\S 1.2.4$: Factorials and binomial coefficients: $1.30$