### 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
1. The '3-shake' 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 '3-shake', or a 'group hug'. What is the total number of possible 3-shakes?
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.

2. Exercise 0.3.7 from your text.

3. Exercise 0.3.23 from your text.

4. 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)
1. Find a recurrence relation for the number of bit strings of length n that do not have two consecutive 0s.
2. What are the initial conditions?
3. How many such bit strings are there of length 5?
4. 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 an be the number of valid n-digit codewords. Find a recurrence relation for an and the initial condition.

• (3) Solve the recurrence relation an = 3an-1 - 2an-2 for n ≥ 2, where a0 = 4 and a1 = 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