Practice Problems for Exam 2

1.Constructive Proof of an Existential Statement

 (a) Prove that there is an even integer n such that n mod 3 = 1.
 (b) Prove that there exists a rational number q such that 9 q^2 = 4.
 (c) Prove that there exist two real numbers whose product is less than their sum.
 (d) Prove that there exist two real numbers which are not equal to each other and whose product is equal to their sum.
 (e) Prove that there is an odd integer n such that n > 1 and n has the form 3k + 1 for some integer k.

2. Direct Proof of a Universal Statement.
 (a) Prove that if n is an integer which is divisible by 6 then n is divisible by 3.
 (b) Prove that for any integers a, b, c, and d, if a divides b and c divides d then a · c divides b · d.
 (c) Prove that the product of two odd integers is odd.
 (d) Prove that if n is an integer which is divisible by 5 then 3n is divisible by 15.
 (e) Prove that for any nonzero rational numbers a and b there is a rational number x such that ax + b = 0.
 (f) Show that the reciprocal of any nonzero rational number is rational.

3. Proof by Cases.
 (a) Prove that for every integer n, n and n + 2 have the same parity (i.e. either n and n + 2 are
both even or n and n + 2 are both odd).
 (b) Prove that for any integer n, n^2 + n is even.
 (c) Prove that for any integers n and m, n^2+3m ≠ 2. Hint: Use an argument by cases depending
on what the remainder is when n is divided by 3.

4. Mathematical Induction.
(a) Prove that for any integer n, if n ≥0 then 4 divides 5^n − 1.
(b) Prove that for any integer n, if n ≥1 then 4 divides 6^n − 2^n.
(c) Show that 2n + 1 < 2^n for every integer n with n ≥3.
(d) Using the fact that 2n+1 < 2^n for every integer n with n ≥3, show that for every integer n,
if n ≥5 then n^2 < 2^n.

5. Strong Mathematical Induction and the Well-Ordering Principle.
(a) Suppose c₀, c₁, c₂, . . . is a sequence defined as follows:
c₀ = 0, c₁ = 1,
c_k= 2c_k-1 − c_k-2 + 2 for all integers k ≥2.
Prove that c_n  = n^2 for all integers n ≥0.
(b) Suppose c₀, c₁, c₂, . . . is a sequence defined as follows:
c₀ = 2, c₁ = 5,
c_k = 5c_k-1 − 6c_k-2 for all integers k ≥2.
Prove that c_n = 2^n + 3^n for all integers n ≥0.

6. Proofs by Contradiction and Contraposition.
(a) Prove that there is no smallest real number x such that 1 < x < 2..
(b) For any integer n, if n2 is not divisible by 3 then n is not divisible by 3.