ALL 10 CHAPTERS COVERED
SOLUTIONS MANUAL
, Instructor’s Manual
with complete solutions
for
Mathematics: A Discrete Introduction
Third Edition
Edward R. Scheinerman
The Johns Hopkins University
This title page will be replaced by Cengage
Version: 2012:03:01:11:12
,To Kelly, Jeff, and Andrew
, Contents
Preface ix
1 Fundamentals 1
1 Joy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Speaking (and Writing) of Mathematics . . . . . . . . . . . . . . . . . . . . . . . 1
3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
4 Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Collections 22
8 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
9 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
10 Sets I: Introduction, Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
11 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
12 Sets II: Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
13 Combinatorial Proof: Two Examples . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Counting and Relations 44
14 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
15 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
16 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
17 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
18 Counting Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
19 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 More Proof 76
20 Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
21 Smallest Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
22 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
23 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
v
SOLUTIONS MANUAL
, Instructor’s Manual
with complete solutions
for
Mathematics: A Discrete Introduction
Third Edition
Edward R. Scheinerman
The Johns Hopkins University
This title page will be replaced by Cengage
Version: 2012:03:01:11:12
,To Kelly, Jeff, and Andrew
, Contents
Preface ix
1 Fundamentals 1
1 Joy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Speaking (and Writing) of Mathematics . . . . . . . . . . . . . . . . . . . . . . . 1
3 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
4 Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
5 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
6 Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
7 Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2 Collections 22
8 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
9 Factorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
10 Sets I: Introduction, Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
11 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
12 Sets II: Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
13 Combinatorial Proof: Two Examples . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Counting and Relations 44
14 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
15 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
16 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
17 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
18 Counting Multisets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
19 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4 More Proof 76
20 Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
21 Smallest Counterexample . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
22 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
23 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
v
