Here are the /Solutions.

This assignment is due Tuesday, September 13th, 2005 at 11:00pm. For due dates of future assignments, see CS202/Assignments.

1. Bureaucratic part

This part you will not be graded on, but you should do it anyway.

Send me email. My address is <aspnes@cs.yale.edu>. In your message, include:

1. Your name.
2. Your status: whether you are an undergraduate, grad student, auditor, etc.

3. Which course you are taking.

4. Whether you have ever taken a class that used Grade-o-Matic before.¹

5. Anything else you'd like to say.

2. Technical part

This part you will be graded on.

1. Prove or disprove: (p \/ q) => (q \/ r) is logically equivalent to (p \/ ¬q) => r.

2. Prove or disprove: for all natural numbers n, n²+2n is a multiple of 3.

3. Prove or disprove: for all natural numbers n, n³+2n is a multiple of 3.

4. Prove or disprove: for all sets A and B, ∅∈A => ∅⊆B.

5. Prove by induction on n that, for any real number x ≥ -1 and any integer n ≥ 1, (1+x)ⁿ ≥ 1 + nx. (Hint: use the fact that a ≥ 0 and b ≥ c implies ab ≥ ac, where a, b, and c are all real numbers.)

Clarification added 2005-09-06: for problems 2 and 3, you should assume that 0 is a natural number (and that it is a multiple of 3).