1.8 The Number of Subsets of a Given Size 21Ifn, k > 0 , then (
n− 1
k− 1
)
+
(
n− 1
k)
=
(
n
k)
; (1.8)
(
n
0)
+
(
n
1)
+
(
n
2)
+···+
(
n
n− 1)
+
(
n
n)
=2n. (1.9)Proof. We prove (1.7) by appealing to the combinatorial meaning of both
sides. We have ann-element set, sayS. The left hand side countsk-element
subsets ofS, while the right hand side counts (n−k)-element subsets of
S. To see that these numbers are the same, we only need to notice that for
everyk-element subset there is a corresponding (n−k)-element subset: its
complement inS, which contains exactly those elements ofSthat are not
contained in thek-element set. This pairs up thek-element subsets with
the (n−k)-element subsets, showing that there is the same number of each.
Let’s prove (1.8) using the algebraic formula (1.6). After substitution,
the identity becomes
n!
k!(n−k)!=
(n−1)!
(k−1)!(n−k)!+
(n−1)!
k!(n−k−1)!.
We can divide both sides by (n−1)! and multiply by (k−1)!(n−k−1)!;
then the identity becomes
n
k(n−k)=
1
n−k+
1
k,
which can be verified by an easy algebraic computation.
Finally, we prove (1.9) through the combinatorial interpretation again.
Again, letSbe ann-element set. The first term on the left-hand side counts
the 0-element subsets ofS(there is only one, the empty set); the second
term counts 1-element subsets; the next term, 2-element subsets, etc. In
the whole sum, every subset ofSis counted exactly once. We know that 2n
(the right-hand side) is the number of all subsets ofS. This proves (1.9),
and completes the proof of Theorem 1.8.2.
1.8.4Find a proof of (1.7) using the algebraic formula forn
k
and a proof of
(1.8), using the combinatorial meaning of both sides.
1.8.5Prove thatn
2
+n+1
2
=n^2 ; give two proofs, one using the combina-
torial interpretation, and the other using the algebraic formula for the binomial
coefficients.
1.8.6Prove (again in two ways) thatn
k
=nkn− 1
k− 1
.1.8.7Prove (in two ways) that for 0≤c≤b≤a,
a
b
b
c
=
a
a−c
a−c
b−c