All answers must be fully justified in complete sentences, except on problems marked with a dagger (†). An expression of the form 3–6† means that the dagger applies to all of problems 3 through 6; something like 7ab† means that the dagger applies to parts a and b of problem 7. Solutions to dagger problems should still be justified, but complete sentences are not required and it should be possible to fit the justification in a single line.
Some problems have a footnote with further explanation.


Lecture 
Assignment 

Week 1 







1 
January 13 
Syllabus 






2 
January 15 
Mathematical definition 






3 
January 17 
Theorems and conjectures 






Week 2 


4 
January 22 
Proof 






5 
January 24 
Disproof 






Week 3 


6 
January 27 
Boolean algebra 






7 
January 29 
Lists 






8 
January 31 
Factorials 






Week 4 


9 
February 3 
Sets and subsets 






10 
February 5 
Quantifiers 






11 
February 7 
Operations on sets 






Week 5 


12 
February 10 
Bijections (combinatorial proof) 



 
13 
February 12 
Review 

Exam 1 
February 13 
Midterm exam 






14 
February 14 
Exam discussion 



HW due Monday, Feb. 17: 


Week 6 

Relations and equivalence 
Scheinerman, §§14–15 

15 
February 17 
Introduction to relations 



HW due Wednesday, Feb. 19: 
§14 (p. 76), #1†, 4†, 12†^{7}, 17† 




§15 (p. 83), #1†, 3†, 7abcf† 



16 
February 19 
Properties of relations 



HW due Friday, Feb. 21: 
§14 (p. 76), #6, 13, 16 




§15 (p. 83), #4, 6, 8abd†, 11 

17 
February 21 
More relations 



HW due Monday, Feb. 24: 
§14 (p. 76), #14, 15 




§15 (p. 83), #16, 17^{8} 



 
Week 7 

Counting partitions and subsets 
Scheinerman, §§16–17 

18 
February 24 
Counting partitions 



HW due Wednesday, Feb. 26: 
§16 (p. 90), #1†, 3, 4, 20 




§17 (p. 98), #1, 3ae, 5†^{10}, 

19 
February 26 
Counting subsets 



HW due Friday, Feb. 28: 
§16 (p. 90), #5, 6, 16 




§17 (p. 98), #6, 7, 10, 14 

20 
February 28 
More counting 



HW due Monday, Mar. 3: 
§17 (p. 98), #17, 33, 35^{11} 




supplemental problems, #1–2 

Week 8 


Scheinerman, §§19–20 

21 
March 3 
Introduction to proof by contradiction 
Scheinerman, §20 



HW due Friday, Mar. 7: 
§20, #2, 9, 11, 13, 16 



22 
March 5 
InclusionExclusion 
Scheinerman, §19 



HW due Friday, Mar. 7: 
§19, #3, 4, 8, 10 

23 
March 7 
More proof by contradiction 
Scheinerman, §20 



HW due Monday, Mar. 10: 
supplemental problems, #1–4 

Week 9 


Scheinerman, §§21–22 

24 
March 10 
Induction I: Smallest counterexample 
Scheinerman, §21 



HW due Wednesday, Mar. 12: 
§21, #1^{12}, 2, 4, 9, 11 

25 
March 12 
Induction II: Proving a proof exists 
Scheinerman, §22 



HW due Friday, Mar. 14: 
§22, #4be, 12, 16af, 23 

26 
March 14 
Induction III 



HW due Monday, Mar. 17: 
§22, #9, 18 




supplemental problems, #1–2 

Week 10 


Scheinerman, §23 and Exam II 

27 
March 17 
Recurrence relations and generating functions 



HW due Wednesday, Mar. 19:  
28 
March 19 
Review 

Exam 2 
March 20 
Midterm exam 

29 
March 21 
Exam discussion 

Spring break! 

Week 11 

Functions 
Scheinerman, §§24, 26 



30 
March 31 
Introduction to functions 



HW due Wednesday, Apr. 2: 
§24, #1acefgh, 2–4†, 8 




§26, #1acfj†, 8 

31 
April 2 
More functions 



HW due Friday, Apr. 4: 
§24, #9, 12, 14bc, 15, 20, 21 

32 
April 4 
Even more functions 



HW due Monday, Apr. 7: 
§24, #16, 17, 22 




§26, #6, 12, 13bc 

Week 12 

Functions, cardinality, and permutations 
Scheinerman, §§25–28 

33 
April 7 
Functions and cardinality 
Scheinerman, §24–26 



HW due Wednesday, Apr. 9: 
§24, #19ab, 23ade^{15}, 24 




§25, #16 




§26, #11 



 
34 
April 9 
The pigeonhole principle 
Scheinerman, §25 



HW due Friday, Apr. 11: 
§25, #1, 3, 5, 9, 11 

35 
April 11 
Cardinality and counting 



HW due Monday, Apr. 14: 
supplemental problems, #1–4 

Week 13 



36 
April 14 
Cardinality 
Scheinerman, §27 





HW due Wednesday, Apr. 16: 
§25, #18, 19 




§27, #3, 7, 10 

37 
April 16 
Cardinality and 
Scheinerman, §§3–7, 11, 20 



HW due Friday, Apr. 18: 
§3, #2 




§5, #11 




§6, #6 




§7, #15†, 17^{16} 




Chapter 1 self test, #12 




supplemental problems, #1–2 

38 
April 18 
Review: Logic 



HW due Monday, Apr. 21: 
§11, #1gi†, 5bfg† 




§20, #1df†, 7, 15, 16a 




§21, #9 

Week 14 



39 
April 21 
Review: Induction 
Scheinerman, §§21–23 



HW due Wednesday, Apr. 23: 
§21, #6 




§22, #4d, 13 




Chapter 4 self test, #17 




supplemental problems, #1–2 

40 
April 23 
Review: Induction 





HW due Friday, Apr. 25: 
Chapter 4 self test, #3, 15 




supplemental problems, #1–2 

41 
April 25 
Review: Set theory 
Scheinerman, §§10, 12, 14–17, 19 



HW due Monday, Apr. 28: 
§10, #1e†, 2d†, 3f† 




§12, #9, 21ag, 30c 




§14, #6 



 
Week 15 

42 
April 28 
Review: Set theory 



HW due Wednesday, Apr. 30: 
§16, #15, 18 




§17, #3c, 18 




§19, #7 




supplemental problems, #1–3 

43 
April 30 
Review: Functions 
Scheinerman, §§17, 23–26 

44 
May 2 
Review: Functions 

Exam 3 
May 3 
Final exam 






^{1}Exercise 12b asks you to analyze the sums of consecutive cubes but shows examples of sums of consecutive odd cubes. You should be looking at the numbers 1^{3}, 1^{3} + 2^{3}, 1^{3} + 2^{3} + 3^{3}, 1^{3} + 2^{3} + 3^{3} + 4^{3}, etc.
^{2}Find a simple formula for the product that does not use the ∏ symbol.
^{3}A name for this condition has already been introduced.
^{4}Prove only the distributive property, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
^{5}Hint: Look back at Theorem 8.2.
^{6}Consider 2element lists drawn from a set of size n.
^{7}Your answer should be exactly one symbol long.
^{8}Hint: A triangle is determined by the lengths of its sides. When do two triples of real numbers (a,b,c) describe similar triangles?
^{9}Make sure to justify your answer with a proof.
^{10}Express your answer as a binomial coefficient and as a formula involving only addition, subtraction, multiplication, and division.
^{11}Try to write a formula that does not rely on the ∏ notation or ellipses. Addition, subtraction, multiplication, division, exponentiation, and the factorial are all fine.
^{12}This is a trick question!
^{13}You don’t need to find a formula; you only need to prove a polynomial exists. Hint: Try using Proposition 23.11 and Theorem 23.17.
^{14}You should assume s ⁄= 1, not s ⁄= 0.
^{15}We know another name for f(A). The question is asking you what this name is.
^{16}Think about this problem using what we now know about functions.