What's New in this Second Edition

In addition to correcting various errors (thank you to all those who wrote!), the following new features have been added:

• Self tests: Every chapter ends with a self test for students. Complete answers appear in Appendix B. These problems are of varying degrees of difficulty. Instructors may wish to specify which problems students should attempt in case not all sections of a chapter have been covered in class.

• A new example proof in Section 4: A number of instructors remarked that the first statements proved (sum of evens is even and transitivity of divisibility) are too simplistic. A new example has been added that is moderately more complicated.

• Section 12 is entirely new and gives a more thorough introduction to combinatorial proof via two nontrivial examples.

• Section 21 on induction has been expanded and made essentially independent of Section 20 on proof by smallest counterexample.

• Section 22 on recurrence relations is entirely new. We develop methods (with full supporting theory) to solve first and second order homogeneous constant coefficient recurrence relations. First order recurrence relations are solved in both the homogeneous and nonhomogeneous cases, while the second order equations are only solved in the homogeneous case (but the more general case is explored in an exercise).

  We also show how to find the formula for the n-th term of a sequence of numbers if that sequence is generated by a polynomial function of n.

• Section 26 includes a new proof that two decompositions of a permutation into transpositions must have the same parity. The new proof avoids the tedious consideration of inversions in a permutation and is based on T.L. Bartlow, An historical note on the parity of permutations, American Mathematical Monthly 79 (1972) 766-769 and S. Nelson, Defining the sign of a permutation, American Mathematical Monthly 94 (1987) 543-545.

• There is a new opening section that describes the pleasure of doing mathematics.

Return to Mathematics: A Discrete Introduction home page.