Description
Exercise 2.1 2 + 2 = 4
Let (N,succ) be a realization of the natural numbers with successor function succ. We define addition of the
numbers 0 and 1 := succ(0) by setting
n + 0 := n, n + 1 := succ(n), n ∈ N.
i) Formulate an inductive definition for n + m, where m, n ∈ N.
(2 Marks)
ii) Set 2 := succ(1), 3 := succ(2), 4 := succ(3). Verify that1
2 + 2 = 4.
(2 Marks)
iii) Prove by induction that n + m = m + n for all m, n ∈ N.
(2 Marks)
Exercise 2.2 Straightforward Induction
Let (an) be the sequence defined by
a1 = 1, a2 = 8 and an = an−1 + 2an−2, n ≥ 3.
Prove that for all n > 0, an = 3 · 2
n−1 + 2(−1)n.
(2 Marks)
Exercise 2.3 The Fifth Peano Axiom
Prove that the induction axiom implies the well-ordering principle.
(3 Marks)
Exercise 2.4 Is a direct induction approach always successful?
Try to prove by induction that for any real number x > −1 and any n ∈ N, (1 + x)
n ≥ nx. If you encounter
difficulties, modify your approach.
(2 Marks)
Exercise 2.5 Strong Induction
Use strong induction to show that every n ∈ N \ {0} can be written as a sum of distinct powers of 2, i.e., as a
sum of a subset of integers 20 = 1, 21 = 2, 22 = 4 etc.
(Hint: For the inductive step, separately consider the case where k + 1 is even and where it is odd. When it is
even, note that (k + 1)/2 ∈ N.)
(3 Marks)
Exercise 2.6 Structural Induction
Let S ⊂ N
2 be defined by
• (0, 0) ∈ S,
• (a, b) ∈ S ⇒
(
((a + 2, b + 3) ∈ S) ∧ ((a + 3, b + 2) ∈ S)
)
.
Use structural induction to show that (a, b) ∈ S implies 5 | (a + b).
(3 Marks)
1The proof of 2+2=4 is due to the German philosopher and mathematician Gottfried Wilhelm Leibniz (1646–1716).
Exercise 2.7 Some easy practice of relation properties
Determine whether the relation R on the set of all integers is reflexive, symmetric and/or transitive, where
(x, y) ∈ R if and only if
i) x + y = 0
ii) 2 | (x − y)
iii) xy = 0
iv) x = 1 or y = 1
v) x = ±y
vi) x = 2y
vii) xy ≥ 0
viii) x = 1
(8 Marks)
