proof of Pascal’s rule
The definition of is the number of -subsets out from an -set. Using this combinatorial meaning the proof is straightforward.
Let a distinct element from the -set. As previously stated, counts the number of subsets with elements, chosen from the set with elements. Now, some of these subsets will contain and some others don’t.
The number of -subsets not containing is , since we need to choose elements from the elements different from .
The number of -subsets containing is , because if it is given that is in the subset, we only need to choose the remaining elements from the elements that are different from .
Thus