Prove or disprove: (p \/ q) => (q \/ r) is logically equivalent to (p \/ ¬q) => r.
Prove or disprove: for all natural numbers n, n2+2n is a multiple of 3.
Prove or disprove: for all natural numbers n, n3+2n is a multiple of 3.
Prove or disprove: for all sets A and B, ∅∈A => ∅⊆B.
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).
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).
Disproof: Let n = 2, then n2+2n = 8, which is not a multiple of 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.
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.
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.)