CSC236

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

## Reviews

There are no reviews yet.