proof of Pascal’s rule

The definition of (nk) 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, (nk) 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 (n-1k), since we need to choose k elements from the n-1 elements different from x.

The number of k-subsets containing x is (n-1k-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.


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