Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Pascal's Identity"

m (→‎Proof: \])
(Still work to be done. In particular, the alternate proof is incomplete and poorly exposited.)
Line 1: Line 1:
−
'''Pascal's Identity''' is a common and useful theorem in the realm of [[combinatorics]] dealing with [[combinations]] (also known as binomial coefficients), and is often used to reduce large, complicated [[combinations]].
+
'''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 [[expression]]s involving binomial coefficients.
  
−
Pascal's identity is also known as Pascal's rule, Pascal's formula, and occasionally Pascal's theorem.
+
Pascal's Identity is also known as Pascal's Rule, Pascal's Formula, and occasionally Pascal's Theorem.
  
 
== Theorem ==
 
== Theorem ==
−
Pascal's identity states that
+
Pascal's Identity states that
  
 
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>
 
<math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>
  
−
for <math>\{ k,n \in \bbfont{N} | k<n \}</math>.
+
for any [[positive integer]]s <math>k</math> and <math>n</math>.  Here, <math>\binom{n}{k}</math> is the binomial coefficient <math>\binom{n}{k} = nCk = C_k^n</math>.
  
−
This can also be read as that the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things.
+
This result can be interpreted combinatorially as follows: the number of ways to choose <math>k</math> things from <math>n</math> things is equal to the number of ways to choose <math>k-1</math> things from <math>n-1</math> things added to the number of ways to choose <math>k</math> things from <math>n-1</math> things.
−
 
 
−
Technically, [[combinations]] can also be applied to non-integer values of <math>k</math>, in which case the identity still holds.
 
  
 
== Proof ==
 
== Proof ==
−
We have <math>\{ k,n \in \bbfont{N} | k<n \}</math>:
+
If <math>k > n</math> then <math>\binom{n}{k} = 0 = \binom{n - 1}{k - 1} + \binom{n - 1}{k}</math> and so the result is trivial.  So assume <math>k \leq n</math>.  Then
  
 
<cmath>\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)!}\\
 
<cmath>\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)!}\\
−
&=&(n-1)!\left[\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right]\\
+
&=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\
−
&=&(n-1)!\frac{n}{k!(n-k)!}\\
+
&=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\
 
&=&\frac{n!}{k!(n-k)!}\\
 
&=&\frac{n!}{k!(n-k)!}\\
−
&=&\binom{n}{k} \qquad\qquad\square\end{eqnarray*}</cmath>
+
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath>
  
−
===Alternate Proof===
+
==Alternate Proof==
 
Here, we prove this using [[committee forming]].
 
Here, we prove this using [[committee forming]].
  

Revision as of 00:08, 31 December 2007

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)!}\\ &=&(n-1)!\left(\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}\right)\\ &=&(n-1)!\cdot \frac{n}{k!(n-k)!}\\ &=&\frac{n!}{k!(n-k)!}\\ &=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}

Alternate Proof

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\]

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.

See Also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Pascal%27s_Identity&oldid=21691"