Examples of Combinatorial Proof
- Pascal's identity:
C(n+1,k) = C(n,k-1) + C(n,k)
- Proof: Suppose T is a set of containing n+1 elements. Let
t is an element of T, and S = T - {t}.
Then we know that there are C(n+1,k) subsets of T containing
k elements. A subset of T with k elements either (1) contains
``t'' together with k-1 elements of S, or (2) contains k
elements of S (and does not contain ``t'').
For case (1), there are C(n,k-1) subsets, and
for case (2), there are C(n,k) subsets. Therefore,
by the sum rule, we have
Pascal's identity: C(n+1,k) = C(n,k-1) + C(n,k).
- The Binomial theorem:
(x+y)^n = sum^n_{j=0} C(n,j) x^{n-j}y^j
- Proof: First we observe that the terms in the product when it is
expanded are of the forms x^{n-j}y^j for j = 0, 1, 2, ..., n.
To count the number of terms of the form x^{n-j}y^j,
note that to obtain such a term it is necessary to choose
n-j x's from n sums x+y, x+y, ..., x+y, (and the other j terms in product
are y's). Therefore, the coefficient of x^{n-j}y^j is
C(n,n-j) = C(n,j).
-
Cardinality of the power set of a finite set:
If S is a finite set with n elements,
then S has 2^n subsets.
- Proof: We observe that a subset of r elements of S is just an unordered
selection of r elements from the set S. Therefore,
by the sum rule and the binomial theorem, we immediately
conclude that the total number of possible subsets is
C(n,0) + C(n,1) + ... + C(n,n) = 2^n