The right‐hand side of (3.15) counts the number of sets of size that can be chosen out of a set of size . Let us take one element of the latter set and label it somehow. We have then a set of unlabeled and labeled element. Each subset of size is one of the following two categories: (1) subsets that contain only unlabeled elements, or (2) subsets that contain unlabeled elements and one labeled element. The two terms on the left‐hand side of (3.15) count the numbers of subsets of the first category and of the second category.
The name Pascal's triangle reflects a way of obtaining the coefficients . We build Pascal's triangle starting with the top row (counted as the zeroth row), which consists of the single number 1 (see Figure 3.1). Then we obtain each number in the subsequent rows as a sum of two numbers directly above it (as marked with arrows in the fifth row). The consecutive numbers in the th row are, reading from the left, the values of
so that, for example, , as marked on the triangle in Figure 3.1. While the Pascal triangle was very useful in the past, today it is of a historical value as statistical packages are used to obtain values of binomial coefficients.
Proof: We will prove the theorem by induction. For , the right‐hand side equals . Assume now that the assertion holds for some , and multiply both sides of (3.16) by . Then
Separating the term for in the first sum, and the term for in the last sum, we may write
