Difference between revisions of "Pascal's Identity"
(Still work to be done. In particular, the alternate proof is incomplete and poorly exposited.) |
|||
| (8 intermediate revisions by 7 users not shown) | |||
| Line 8: | Line 8: | ||
<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 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} = | + | 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} = {}_nC_k = C_k^n</math>. |
| − | 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. | + | 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. |
== Proof == | == Proof == | ||
| Line 21: | Line 21: | ||
&=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath> | &=&\binom{n}{k}. \qquad\qquad\square\end{eqnarray*}</cmath> | ||
| − | ==Alternate | + | ==Alternate Proofs== |
Here, we prove this using [[committee forming]]. | Here, we prove this using [[committee forming]]. | ||
| Line 31: | Line 31: | ||
<cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} \qquad \qquad \square</cmath> | <cmath>{n \choose k}={n-1\choose k-1}+{n-1\choose k} \qquad \qquad \square</cmath> | ||
| + | |||
| + | |||
| + | 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 <math>\binom{n}{k}</math>. Above that, we would see the terms <math>{n-1\choose k-1}</math> and <math>{n-1\choose k}</math>. Due to the definition of Pascal's Triangle, <math>{n \choose k}={n-1\choose k-1}+{n-1\choose k}</math>. | ||
==History== | ==History== | ||
| − | Pascal's identity was probably first derived by [[Blaise Pascal]], a | + | Pascal's identity was probably first derived by [[Blaise Pascal]], a 17th 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]]. | 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]]. | ||
| Line 41: | Line 44: | ||
*[[Combination]] | *[[Combination]] | ||
*[[Committee forming]] | *[[Committee forming]] | ||
| + | *[[Combinatorial_identity#Hockey-Stick_Identity]] | ||
| + | |||
==External Links== | ==External Links== | ||
| − | *[ | + | *[https://planetmath.org/pascalsrule Pascal's Identity at Planet Math] |
*[http://mathworld.wolfram.com/PascalsFormula.html Pascal's Identity at Wolfram's Math World] | *[http://mathworld.wolfram.com/PascalsFormula.html Pascal's Identity at Wolfram's Math World] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
[[Category:Theorems]] | [[Category:Theorems]] | ||
Latest revision as of 14:43, 11 April 2024
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
for any positive integers 
and 
. Here, 
is the binomial coefficient 
.
This result can be interpreted combinatorially as follows: the number of ways to choose things from things is equal to the number of ways to choose 
things from 
things added to the number of ways to choose things from things.
Proof
If 
then 
and so the result is trivial. So assume 
. Then
Alternate Proofs
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} \qquad \qquad \square\]](http://latex.artofproblemsolving.com/b/c/2/bc287965cf3654fa5d3daaeaa5d714dcca2cb3c1.png)
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 . Above that, we would see the terms 
and 
. Due to the definition of Pascal's Triangle, .
History
Pascal's identity was probably first derived by Blaise Pascal, a 17th 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.
