Homework assignments

You can expect each assignment to be posted to this page at least a week before it is due. Please contact me immediately if you have any trouble getting the assignment.

Sections and problem numbers refer to your assigned text. Recall that there are hints and answers to selected problems in the back of your text.

Problems marked with an asterisk are more advanced problems. (For example, in Assignment 2, problems 10b and 10c are advanced.) Many of you will be able to do these, and I would encourage all of you to try them. But don't panic if you try hard on them and can't get them. It would be better to spend more time on the other problems rather than spending a lot of time on asterisked problems.

Homework is due by 4:15 pm (under the door in my office), or you can feel free to turn it in earlier in the day, in class.

Assignment 1, due Monday, January 13

Part of the assignment is to carefully read the relevant sections of the text!
Section 1.1
5, 6, 7d, 7f, 8, 15a, 15c, 15f, 16, 17, 18, 21.
Please don't bother learning the details of the "POSTNET" system. Just read the "POSTNET" example as an illustration of the ideas of the chapter.
For Problems 5, 6, and 7: No "prose" is necessary, but do 6 "by hand."
About Problem 8: These can be proven by mathematical induction. Part a can also be proved in a "cooler" way that you may be familiar with. Is there a clever way to do part b without induction? In any case, you must write at least one of these proofs as a formal induction. Also, in part c, what is the integer?

I think it's fair to warn you that Assignment 1 is easier than what you should usually expect, since we haven't learned much yet. Assignment 2 is a better example of a typical assignment.

Assignment 2, due Monday, January 27

Part of the assignment is to carefully read the relevant sections of the text, except that on 1.3, you only need to read up to Example 1.3.7.
Section 1.2
9b, 10a, 10b^*, 10c^*, 17, 18, 26, 28.
For 10a, 10b and 10c, you must give a combinatorial proof. Think about what each side of the formula counts. I'll get you started: The left side of 10a counts how many ways you can choose a k-element subset S of [n] and then choose an r-element subset T of S. Problem 10c is significantly harder than 10a and 10b.
For 28, you actually need another assumption for this to be correct: assume all the a_i's are greater than zero. Also, to make clear exactly what Problem 28 is asking: if we were factoring 6, we would count "2 times 3" and "3 times 2" as the same factorization.
Section 1.3
15, 17, 18.