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, 178 |
||||||
|
|
| |||||||
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, 3511 |
||||||
|
|
|
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 |
Inclusion-Exclusion |
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, #112, 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, 23ade15, 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†, 1716 |
||||||
|
|
|
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 |
|||||||
|
|||||||||
|
|||||||||
|
1Exercise 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 13, 13 + 23, 13 + 23 + 33, 13 + 23 + 33 + 43, etc.
2Find a simple formula for the product that does not use the ∏ symbol.
3A name for this condition has already been introduced.
4Prove only the distributive property, A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
5Hint: Look back at Theorem 8.2.
6Consider 2-element lists drawn from a set of size n.
7Your answer should be exactly one symbol long.
8Hint: A triangle is determined by the lengths of its sides. When do two triples of real numbers (a,b,c) describe similar triangles?
9Make sure to justify your answer with a proof.
10Express your answer as a binomial coefficient and as a formula involving only addition, subtraction, multiplication, and division.
11Try to write a formula that does not rely on the ∏ notation or ellipses. Addition, subtraction, multiplication, division, exponentiation, and the factorial are all fine.
12This is a trick question!
13You 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.
14You should assume s ⁄= 1, not s ⁄= 0.
15We know another name for f(A). The question is asking you what this name is.
16Think about this problem using what we now know about functions.