Assignment #1: Induction

The aim of this assignment is to give you some practice with various forms
of induction. For each question below you will present a proof by induction,
using the type of induction specified. For full marks on your proofs, you will
need to make it clear to the reader that the base case(s) is/are verified, that
the inductive step follows for each element of the domain (typically the natural
numbers), where the inductive hypothesis is used and that it is used in a valid
case.
Your assignment must be typed to produce a PDF document a1.pdf (handwritten submissions are not acceptable). You may work on the assignment in
groups of 1, 2, or 3, and submit a single assignment for the entire group on
MarkUs.
1. Consider the Fibonacci function f:
f(n) = (
1, if n = 0 or n = 1
f(n − 2) + f(n − 1) if n 1
Use simple induction to prove that if n is a natural number, then f(0) +
f(2) + · · · + f(2n) = f(2n + 1).
You may not derive or use a closed-form for f(n) in your proof.
2. Use simple induction to show that x
2 − 1 is divisible by 8 for any odd
natural number x.
3. Can we represent any amount with coins of denominations 3 and 5? If
yes, prove your answer, if not, can we find a number that any amount
greater or equal to it we can represented it with the above coins? Prove
your answer.
4. Use the Well-Ordering Principle to show that given any natural number
n ≥ 1, there exists an odd integer m and a natural number k such that
n = 2k ∗ m.
5. Define a set M ⊆ Z
2 as follows:
(a) (3, 2) ∈ M,
(b) for all (x, y) ∈ M, (3x − 2y, x) ∈ M,
1
(c) nothing else belongs to M.
Use structural induction to prove that ∀(x, y) ∈ M, ∃k ∈ N,(x, y) =
(2k+1 + 1, 2
k + 1).
6. Suppose n people are positioned such that each person has a unique nearest neighbour. Each person has a single water balloon that they throw at
their nearest neighbour. (We’ll assume every throw hits its target.) A dry
person is one who is not hit by a water balloon.
(a) Describe an example that demonstrates than if n is even, there may
be no dry person.
(b) Use simple induction to show that if n is odd, then there is always
at least one dry person.
7. Let P be a convex polygon with consecutive vertices v1, v2, ..., vn. Use
complete induction to show that when P is triangulated into n−2 triangles,
the n − 2 triangles can be numbered 1, 2, ..., n − 2 so that vi
is a vertex of
triangle i for i = 1, 2, ..., n − 2.
2