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).

1. Disproof: Let p, q, and r all be false. Then (p \/ q) => (q \/ r) is true (both sides of the implication are false) but (p \/ ¬q) => r is false (the left-hand side is true but the right-hand side is false).

2. Disproof: Let n = 2, then n²+2n = 8, which is not a multiple of 3.

3. Proof: By induction on n. Base case is n = 0, where n³+2n = 0 is a multiple of 3. Induction step: From the induction hypothesis, assume n³+2n = 3k for some k. Now consider (n+1)³ + 2(n+1) = n³ + 3n² + 3n + 1 + 2n + 2 = (n³ + 2n) + 3n² + 3n + 3 = 3(k + n² + n + 1), which is a multiple of 3.

4. Proof: Recall that ∅⊆B is defined as ∀x x∈∅ => x∈B. But no x is an element of ∅, so the implication is vacuously true. It follows that ∅⊆B for all B, and thus that the implication to be proved is true for all A and B.

5. The base case is n = 1; here we have (1+x)ⁿ = 1+x = 1+nx. For the induction step, suppose that (1+x)ⁿ ≥ 1+nx, and consider (1+x)ⁿ⁺¹ = (1+x)(1+x)ⁿ ≥ (1+x)(1+nx) = 1 + nx + x + nx² ≥ 1+(n+1)x. (For the first inequality, we use the fact that x ≥ -1 means (1+x) ≥ 0; for the second, we use the fact that x² ≥ 0 for all x.)