Pascal's Identity

From AoPSWiki

Revision as of 18:44, 26 May 2009 by WrathOfMobius (Talk | contribs)

(diff) ← Older revision | Current revision (diff) | Newer revision → (diff)

Pascal's Identity is a useful theorem of combinatorics dealing with combinations (also known as binomial coefficients). It can often be used to simplify complicated expressions involving binomial coefficients.

Pascal's Identity is also known as Pascal's Rule, Pascal's Formula, and occasionally Pascal's Theorem.

Theorem

Pascal's Identity states that

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

for any positive integers $k$ and $n$ . Here, $\binom{n}{k}$ is the binomial coefficient $\binom{n}{k} = nCk = C_k^n$ .

This result can be interpreted combinatorially as follows: the number of ways to choose $k$ things from $n$ things is equal to the number of ways to choose $k-1$ things from $n-1$ things added to the number of ways to choose $k$ things from $n-1$ things.

Proof

If $k > n$ then $\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}$ and so the result is trivial. So assume $k \leq n$ . Then

$\begin{eqnarray*}\binom{n-1}{k-1}+\binom{n-1}{k}&=&\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}\\&=&...$

Alternate Proofs

Here, we prove this using committee forming.

Consider picking one fixed object out of $n$ objects. Then, we can choose $k$ objects including that one in $\binom{n-1}{k-1}$ ways.

Because our final group of objects either contains the specified one or doesn't, we can choose the group in $\binom{n-1}{k-1}+\binom{n-1}{k}$ ways.

But we already know they can be picked in $\binom{n}{k}$ ways, so

${n \choose k}={n-1\choose k-1}+{n-1\choose k} \qquad \qquad \square$

Also, we can look at Pascal's Triangle to see why this is. If we were to extend Pascal's Triangle to row n, we would see the term $\binom{n}{k}$ . Above that, we would see the terms ${n-1\choose k-1}$ and ${n-1\choose k}$ . Due to the definition of Pascal's Triangle, ${n \choose k}={n-1\choose k-1}+{n-1\choose k}$ .

History

Pascal's identity was probably first derived by Blaise Pascal, a 19th century French mathematician, whom the theorem is named after.

Pascal also did extensive other work on combinatorics, including work on Pascal's triangle, which bears his name. He discovered many patterns in this triangle, and it can be used to prove this identity. The method of proof using that is called block walking.

External Links

Personal tools

Navigation

Search

Toolbox