Topic 2: Techniques of proof
—
Practice exercises
Exercise 1
Distinguish in each of the following cases what are the hypotheses or premises, and the conclusions
(the statements may be meaningless or erroneous):
a) Let x be a rational number. If x is leafy, then x is not an integer.
b) If an integer is divisible by 3 and by 5, then it is divisible by 20.
c) All non-zero integers divisible by 3 are even.
d) Let n and m be integers. Then n/m is a rational number.
e) Suppose x and y are positive real numbers. Then, if they are leafy, xy will be an integer, and x/y
will be rational.
Exercise 2
We say an integer n is odd if there is some integer k such that n = 2k + 1. And we say an integer n
is even if there is some integer k such that n = 2k. Prove that the sum of two odd numbers is an
even number stating each step carefully.
Exercise 3
Show that the sum of two consecutive odd numbers is a multiple of 4.
Exercise 4
Use the following definition:
Def. Let a and b be integers. We say a divides b if there is some integer q such that aq=b. If
a divides b, we write a | b, and we say that b is divisible by a.
to prove the following statements (assume n and m to be integers):
a) 1 | n
b) n | n
c) If m | n, then m | -n
Exercise 5
Let a, b, c, m and n be integers. Show that if a | b and a | c, then a | (bm + cn).
Exercise 6
Prove that if n is an integer, then 2n 2 + n + 1 is not divisible by 3.
Exercise 7 **
Let x be a real number. Define the absolute value of x, denoted |x|, by
Calculate the following:
|1|, |-1|, |0|, |3986|, |-π|, |-0.5|, |1/2|
Let r and s be real numbers. Prove the following statements using proof by cases:
(1) |-r| = | r|
(2) |r|2 = r2
(3) r≤|r|
(4) |rs| = |r||s|
(5) |r + s| ≤ |r|+|s|
Exercise 7 (bis)
Prove that if a, b ∈ ℤ, then a 4 − 4b ≠ 2.
Exercise 8
Prove that 6 is irrational.
Exercise 9 **
Prove that if n ∈ ℤ, 4 ∤ (n 2 + 2).
Exercise 10.
Let n be an integer number. If the number 7n + 4 is even, then n is even.
Exercise 11
Let a, b and c be integers. Show that if a does not divide bc, then a does not divide b.
Exercise 12
Let x and y be real numbers. If xy is irrational, then x or y is irrational.
Exercise 13 **
Let m and n be two integers. If they are consecutive, then their sum, m+n, is an odd number. Prove
this using both the direct method and contrapositive.
Exercise 14
Show that the product of two integers is even if and only if one of them is even.
Exercise 15 **
Let a and b be two distinct real numbers. Consider the following statements:
(a) a and b are either both even or both odd
(b) a + b is even
(c) a - b is even
Prove that (a) ⇒ (b), that (b) ⇒ (c) and that (c) ⇒ (a).
Explain why this means that the three statements are equivalent, i.e. that (a) ⇔ (b), (b) ⇔ (c) and
(c) ⇔ (a).
Exercise 16
Prove by induction that ∀k ≥ 1, 1 + 2 + 22 + 23 + . . . + 2k−1 = 2k − 1.
Exercise 17
Let a, b ∈ ℕ. Show that a n − b n is divisible by a - b for all n ∈ ℕ.
Exercise 18
Show that 3n > 1 + 2n for all n ∈ ℕ.
Exercise 19 **
Prove by induction that the following formulas hold for all n ≥ 1:
(a) 2 + 4 + 6 + . . . + 2n = n 2 + n
(b) 13 + 33 + 53 + . . . + (2n − 1)3 = n 2(2n 2 + 1)
1 1 1 1 n
(c) + + + ... + =
1⋅2 2⋅3 3⋅4 n ⋅ (n + 1) n+1
Exercise 20 **
Prove the following inequalities:
(a) n 3 + 1 > n 2 + n for all n ∈ ℕ such that n ≥ 2.
(b) 2n > 7n for all n ∈ ℕ such that n ≥ 6.
Exercise 21
The symbol ∑ denotes the sum of different terms, for example, we could rewrite the expressions in
Ex 17 as:
n
2i = n 2 + n
∑
(a)
i=1
n
(2i − 1)3 = n 2(2n 2 − 1)
∑
(b)
i=1
n
1 n
∑ i(i + 1)
(c) =
i=1
n+1
Where i is an index number that runs from 1 to n as the terms are added up.
Show that
n
i n+2
∑ 2i
= 2 −
i=1
2n
for all n ∈ ℕ.
Exercise 22
Prove or give a counterexample to each of the following statements:
(a) For each integer a, there exists an integer b such that a|b.
(b) There exists an integer b such that for all integers a, we have a|b.
(c) For each integer b, there exists an integer a such that a|b.
(d) There exists an integer a such that for all integers b, we have a|b.
Exercise 23
Prove that ∃!x ∈ ℝ such that x 2 + 1 = 2x. Differentiate the scratch work from the proof.
Exercise 24
Give a counterexample to the statement "If n is an integer and n 2 is divisible by 4, then n is
divisible by 4."
Exercise 25
Give a counterexample to the statement "If a and b are real numbers, then (a + b)2 = a 2 + b 2"
Exercise 26 **
Write the following statements with quantifiers and prove them:
(a) There exists a real number y such that for every real number 𝑥, we have e x > y.
(b) For every real number 𝑥 there is a unique real number 𝑦 such that x 2 = y + 2.
(c) There is a unique number y such that for every real number 𝑥, we have x y = − x.
(d) For every real number 𝑥 there is a unique real number 𝑦 such that e x − y = 0.
(e) For every real number 𝑥 there is a real number 𝑦 such that (𝑥+1)3 − 𝑥3=3𝑦 + 1.
Exercise 27
Suppose x and y are rational numbers and x < y. Prove that there exists z ∈ Q such that x < z < y.
That is, prove that between every two rationals there exists another rational.
Exercise 28**
Prove or give a counterexample to each of the following statements:
(a) For every real number x there exists a real number y such that x < y
(b) For every real number x > 0 there exists a real number y < 0 such that x 2 + x − 1 = y.
(c) There exists a real number y ≥ 1 such that for all real numbers x ≥ 1, y < x.
(d) There exists a real number y such that for all real numbers x, we have x 2 + x + 1 = y.
