# proof of Pascal’s rule

The definition of $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ is the number of $k$-subsets out from an $n$-set. Using this combinatorial meaning the proof is straightforward.

Let $x$ a distinct element from the $n$-set. As previously stated, $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ counts the number of subsets with $k$ elements, chosen from the set with $n$ elements. Now, some of these subsets will contain $x$ and some others don’t.

The number of $k$-subsets not containing $x$ is $\left(\genfrac{}{}{0pt}{}{n-1}{k}\right)$, since we need to choose $k$ elements from the $n-1$ elements different from $x$.

The number of $k$-subsets containing $x$ is $\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right)$, because if it is given that $x$ is in the subset, we only need to choose the remaining $k-1$ elements from the $n-1$ elements that are different from $x$.

Thus

$$\left(\genfrac{}{}{0pt}{}{n}{k}\right)=\left(\genfrac{}{}{0pt}{}{n-1}{k}\right)+\left(\genfrac{}{}{0pt}{}{n-1}{k-1}\right).$$ |

Title | proof of Pascal’s rule |
---|---|

Canonical name | ProofOfPascalsRule |

Date of creation | 2013-03-22 15:03:11 |

Last modified on | 2013-03-22 15:03:11 |

Owner | drini (3) |

Last modified by | drini (3) |

Numerical id | 5 |

Author | drini (3) |

Entry type | Proof |

Classification | msc 05A19 |