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

Prove or disprove: for all natural numbers n, n

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

^{3}+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 n

^{2}+2n = 8, which is not a multiple of 3.Proof: By induction on n. Base case is n = 0, where n

^{3}+2n = 0 is a multiple of 3. Induction step: From the induction hypothesis, assume n^{3}+2n = 3k for some k. Now consider (n+1)^{3}+ 2(n+1) = n^{3}+ 3n^{2}+ 3n + 1 + 2n + 2 = (n^{3}+ 2n) + 3n^{2}+ 3n + 3 = 3(k + n^{2}+ 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 + nx^{2}≥ 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^{2}≥ 0 for all x.)