## Math 2001 — Spring 2014 Assignments

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

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, 8c†2, 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

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

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

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:

§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
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

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.

8Hint: A triangle is determined by the lengths of its sides. When do two triples of real numbers (a,b,c) describe similar triangles?

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.