Pascal's Rule

From ProofWiki
Jump to: navigation, search

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}$


Complex Numbers

For all $z, w \in \C$ such that it is not the case that $z$ is a negative integer and $w$ an integer:

$\dbinom z {w - 1} + \dbinom z w = \dbinom {z + 1} w$

where $\dbinom z w$ is a binomial coefficient.


Direct Proof

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

\(\displaystyle \binom n k + \binom n {k - 1}\) \(=\) \(\displaystyle \frac {n!} {k! \, \paren {n - k}!} + \frac {n!} {\paren {k - 1}! \, \paren {n - \paren {k - 1} }!}\) $\quad$ Definition of Binomial Coefficient $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n! \, \paren {n - \paren {k - 1} } } {k! \, \paren {n - k}! \, \paren {n - \paren {k - 1} } } + \frac {n! \, k} {\paren {k - 1}! \, \paren {n - \paren {k - 1} }! \ k}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n! \, \paren {n - k + 1} } {k! \, \paren {n - k + 1}!} + \frac {n! \, k} {k! \, \paren {n - k + 1}!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n! \, \paren {n - k + 1} + n! \, k} {k! \, \paren {n - k + 1}!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n! \, \paren {n - k + 1 + k} } {k! \, \paren {n - k + 1}!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {n! \, \paren {n + 1} } {k! \, \paren {n - k + 1}!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \frac {\paren {n + 1}!} {k! \, \paren {n + 1 - k}!}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \binom {n + 1} k\) $\quad$ Definition of Binomial Coefficient $\quad$

$\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 $\dbinom {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 $\dbinom 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 $\dbinom n {k - 1}$ ways of selecting the other $k - 1$ members so as to form such a committee.


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

Hence the result.

$\blacksquare$


Proof for Real Numbers

\(\displaystyle \left({r + 1}\right) \binom r {k - 1} + \left({r + 1}\right) \binom r k\) \(=\) \(\displaystyle \left({r + 1}\right) \binom r {k - 1} + \left({r + 1}\right) \binom r {r - k}\) $\quad$ Symmetry Rule for Binomial Coefficients $\quad$
\(\displaystyle \) \(=\) \(\displaystyle k \binom {r + 1} k + \left({r - k + 1}\right) \binom {r + 1} {r - k + 1}\) $\quad$ Factors of Binomial Coefficient $\quad$
\(\displaystyle \) \(=\) \(\displaystyle k \binom {r + 1} k + \left({r - k + 1}\right) \binom {r + 1} k\) $\quad$ Symmetry Rule for Binomial Coefficients $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({r + 1}\right) \binom {r + 1} k\) $\quad$ $\quad$

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

$\blacksquare$


Also known as

Some sources give this as Pascal's identity.


Also presented as

Some sources present this as:

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


Also see


Source of Name

This entry was named for Blaise Pascal.


Sources