ABSTRACT

Exercise 419: The reader likely does not need to be reminded that an inductive proof is not the preferred method here; however, it may be an interesting exercise to show that induction can be used to prove the result nevertheless. Let “N -set” be an abbreviation for “set with N elements”. A proof is by induction on n the statement S(n): For every k satisfying 0 ≤ k ≤ n, the number of distinct k-sets in an n-set is

) .