Math 2001 — Spring 2014
Assignments

Last revised: April 28, 2014 at 1:06pm

Warning: This table will change as the semester progresses! Consult the course website for an up-to-date version of this file. If you are viewing this file in a web browser, press reload to make sure you are viewing the most updated version.

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





HW:Bring clickers to the first class
Read: Syllabus

1

January 13

Syllabus
What is mathematics?
How to read a math text

Read:Scheinerman, 1–3 (pp. 1–6)

2

January 15

Mathematical definition

HW:3 (p. 6), #1–6, 12, 13
Read: Scheinerman, 4 (pp. 8–13)

3

January 17

Theorems and conjectures

HW:4 (p. 13), #1abcg, 2adegijk,
7, 10, 121
Read:Scheinerman, 5 (pp. 15–22)




Week 2





4

January 22

Proof

HW:5 (p. 22), #1, 7, 16, 18, 21
Read: Scheinerman, 6 (pp. 23–24)

5

January 24

Disproof

HW:6 (p. 24), #2, 4, 5, 10, 12
Read: Scheinerman, 7 (pp. 25–28)




Week 3





6

January 27

Boolean algebra

HW:7 (p. 28), #4, 10a, 11ef,
12ef, 16, 17, 20abc
Read:Scheinerman, 8 (pp. 33–38)

7

January 29

Lists

HW:8 (p. 38), #5, 9, 13, 16
Read: Scheinerman, 9 (pp. 40–42)

8

January 31

Factorials

HW:9 (p. 42), #1, 4, 5, 6, 8c2,
11, 13, 15
Read:Scheinerman, 10 (pp. 43–50)




Week 4





9

February 3

Sets and subsets

HW:10 (p. 50), #1–6, 7, 113, 14
Read:Scheinerman, 11 (pp. 51–54)

10

February 5

Quantifiers

HW:11 (p. 54), #1abgj,2eik,4,5ae,
6,7,8abc
Read:Scheinerman, 12 (pp. 56–64)

11

February 7

Operations on sets

HW:12 (p. 64), #1, 54, 6, 9, 20, 25
Read:Scheinerman, 13 (pp. 66–69)




Week 5





12

February 10

Bijections (combinatorial proof)

HW:12 (p. 64), 295, 30ab
13 (p. 69), #2, 4, 56, 7

13

February 12

Review

Exam 1

February 13

Midterm exam

Read:Scheinerman, 14 (pp. 73–76)

14

February 14

Exam discussion

HW due Monday, Feb. 17:

Do Exam 1 as homework.




Week 6

Relations and equivalence
relations

Scheinerman, 14–15





15

February 17

Introduction to relations

HW due Wednesday, Feb. 19:

14 (p. 76), #1, 4, 127, 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

Quiz 17, #49, 6





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, 510,

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:

23, #4, 5, 7, 813, 1014

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

supplemental problems, #1

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
Review: Logic

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

supplemental problems, #1





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.