Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

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

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

3. Prove or disprove: for all natural numbers n, n3+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)n ≥ 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 n2+2n = 8, which is not a multiple of 3.

3. Proof: By induction on n. Base case is n = 0, where n3+2n = 0 is a multiple of 3. Induction step: From the induction hypothesis, assume n3+2n = 3k for some k. Now consider (n+1)3 + 2(n+1) = n3 + 3n2 + 3n + 1 + 2n + 2 = (n3 + 2n) + 3n2 + 3n + 3 = 3(k + n2 + 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)n = 1+x = 1+nx. For the induction step, suppose that (1+x)n ≥ 1+nx, and consider (1+x)n+1 = (1+x)(1+x)n ≥ (1+x)(1+nx) = 1 + nx + x + nx2 ≥ 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 x2 ≥ 0 for all x.)

2014-06-17 11:57