Difference between revisions of "Pascal's Identity"
(super-expand) |
|||
| 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 also known as Pascal's Rule, Pascal's Formula, and occasionally Pascal's Theorem. | ||
| + | |||
| + | == Theorem == | ||
Pascal's Identity states that | Pascal's Identity states that | ||
| Line 5: | Line 10: | ||
for <math>\{ k,n \in \bbfont{N} | k<n \}</math> | for <math>\{ k,n \in \bbfont{N} | k<n \}</math> | ||
| − | {{ | + | == Proof == |
| + | We have <math>\{ k,n \in \bbfont{N} | k<n \}</math>: | ||
| + | |||
| + | <math>\binom{n-1}{k-1}+\binom{n-1}{k}=\frac{(n-1)!}{(k-1)!(n-k)!}+\frac{(n-1)!}{k!(n-k-1)!}</math> | ||
| − | [ | + | <math>=(n-1)!\left[\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}</math> |
| − | [[ | + | <math>=(n-1)!\frac{n}{k!(n-k)!}</math> |
| + | |||
| + | <math>=\frac{n!}{k!(n-k)!}</math> | ||
| + | |||
| + | <math>=\binom{n}{k}</math> | ||
| + | |||
| + | {{halmos}} | ||
| + | ===Alternate Proof=== | ||
| + | Here, we prove this using [[committee forming]]. | ||
| + | |||
| + | Consider picking one fixed object out of <math>n</math> objects. Then, we can choose <math>k</math> objects including that one in <math>\binom{n-1}{k-1}</math> ways. | ||
| + | |||
| + | Because our final group of objects either contains the specified one or doesn't, we can choose the group in <math>\binom{n-1}{k-1}+\binom{n-1}{k}</math> ways. | ||
| + | |||
| + | But we already know they can be picked in <math>\binom{n}{k}</math> ways, so | ||
| + | |||
| + | <cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</cmath> | ||
| + | |||
| + | {{halmos}} | ||
| + | ==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, which is why [[Pascal's Triangle]] is named after him. | ||
| + | ==See Also== | ||
| + | *[[Combinatorics]] | ||
| + | *[[Combination]] | ||
| + | *[[Committee forming]] | ||
| + | ==External Links== | ||
| + | *[http://planetmath.org/encyclopedia/PascalsRule.html Pascal's Identity at Planet Math] | ||
| + | *[http://mathworld.wolfram.com/PascalsFormula.html Pascal's Identity at Wolfram's Math World] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
| + | [[Category:Theorems]] | ||
Revision as of 20:32, 8 December 2007
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 also known as Pascal's Rule, Pascal's Formula, and occasionally Pascal's Theorem.
Theorem
Pascal's Identity states that
for $\{ k,n \in \bbfont{N} | k<n \}$ (Error compiling LaTeX. Unknown error_msg)
Proof
We have $\{ k,n \in \bbfont{N} | k<n \}$ (Error compiling LaTeX. Unknown error_msg):
$=(n-1)!\left[\frac{k}{k!(n-k)!}+\frac{n-k}{k!(n-k)!}$ (Error compiling LaTeX. Unknown error_msg)
∎
Alternate Proof
Here, we prove this using committee forming.
Consider picking one fixed object out of 
objects. Then, we can choose 
objects including that one in 
ways.
Because our final group of objects either contains the specified one or doesn't, we can choose the group in 
ways.
But we already know they can be picked in 
ways, so
![\[{n \choose k}={n-1\choose k-1}+{n-1\choose k}\]](http://latex.artofproblemsolving.com/b/9/e/b9e814ea2d14ccaf430a823f7e86364bb1018a6b.png)
∎
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, which is why Pascal's Triangle is named after him.
