Math 250 Homework Assignments

HW A Write a short (at most one
page) introduction of yourself, including your
background in both mathematics and computer science,
why you are taking this course, and what you hope to
learn in this course. Submit this via Kit.

HW 1
 The '3shake' problem: A group of 6 strangers are
meeting for the first time. To get to know each other,
they break up into smaller groups of 3 to chat. They do
this in all the ways possible. Such a group is
called a '3shake', or a 'group hug'. What is the
total number of possible 3shakes?
NOTE: Think about this and come up with a counting
scheme that leads you to the answer, and explain your
method succinctly. So do this without any help other
than from your classmates/me. Don't simply look
up a formula you think might apply.
 Exercise 0.3.7 from your text.
 Exercise 0.3.23 from your text.
 Exercise 0.3.27 from your text.

HW 2
These exercises are all from the text.
 Exercise 1.1.4
 Exercise 1.1.10
 Exercise 1.2.4
 Exercise 1.3.4
 Exercise 1.3.6
 Exercise 1.3.9

HW 3
These are all exercises from the text.
 Exercise 1.4.9
 Exercise 1.4.10
 Exercise 1.5.3
 Exercise 1.5.5
 Exercise 1.5.7
 Exercise 1.6.2
 Exercise 1.6.4

HW 4
These are all exercises from the text.
 Exercise 2.1.11
 Exercise 2.1.17
 Exercsie 2.2.1
 Exercise 2.2.7
 Exercise 2.2.10
 Exercise 2.2.12

HW 5
 (1)
 Find a recurrence relation for the number of bit
strings of length n that do not have two
consecutive 0s.
 What are the initial conditions?
 How many such bit strings are there of length 5?
 What sequence is this similar to? Explain.
 (2) A computer system considers a string of decimal
digits a valid codeword it it contains an even number of
0 digits. For instance, 1230407869 is valid, whereas
120987046608 is not valid. Let a_{n} be the
number of valid ndigit codewords. Find a
recurrence relation for a_{n} and the initial
condition.
 (3) Solve the recurrence relation a_{n} =
3a_{n1}  2a_{n2} for n ≥ 2, where
a_{0} = 4 and a_{1} = 1.

HW 6
These are all exercises from the text. Your proofs should
be written using complete sentences mixed with mathematical
statements.
 Exercsise 2.5.7
 Exercise 2.5.10
 Exercise 2.5.16
 Exercise 2.5.17
 Exercise 2.5.29

HW 7
These are all exercises from the text.
 Exercise 0.2.18
 Exercise 0.2.19
 Exercise 0.2.20
 Exercise 3.1.4
 Exercise 3.1.5
 Exercise 3.1.9
 Exercise 3.1.10
 Exercise 3.1.15
 Exercise 3.1.18