proof of Pascal’s rule

The definition of $\binom{n}{k}$ 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, $\binom{n}{k}$ 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 $\binom{n-1}{k}$ , since we need to choose $k$ elements from the $n-1$ elements different from $x$ .

The number of $k$ -subsets containing $x$ is $\binom{n-1}{k-1}$ , 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

$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}.$

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