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_{0}, c_{1}, c_{2}, . . . is a sequence defined as follows:

c_{0} = 0, c_{1} = 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_{0}, c_{1}, c_{2}, . . . is a sequence defined as follows:

c_{0} = 2, c_{1} = 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.