## Description

The aim of this assignment is to give you some practice with various avours

of induction. Be sure to read each question carefully, and use the proof technique specied. For example, if a question asks you to prove a claim via complete

induction, no marks will be awarded for a correct proof using a dierent technique. If a question simply says to use `induction’, you may choose whatever

techniques from among fsimple induction, complete induction, well-ordering,

structural inductiong you nd appropriate.

Assignments are to be completed individually and typeset in LATEX. The

.tex source le and rendered pdf should both be uploaded to MarkUs. For

further details, see the course website: http://www.cs.toronto.edu/~colin/

236/W20/assignments/.

1. Dene function f recursively as follows:

f(n) = (

1 if n 1

n f(n 2) if n > 1

Use induction to prove that for all even n 2 N, f(n) = 2n=2

(n=2)!.

2. What happens when the fall of the nth domino implies the fall of the

previous one? Suppose we have proven the following facts with respect

to some predicate P(n):1

P(1) (1)

8n 2 N

+; P(n) =) P(n 1) (2)

8n 2 N; P(n) =) P(2n) (3)

In this question, you will show that, taken together, these three statements

comprise a valid proof that P holds for all natural numbers.

(a) Use complete induction to prove that 8n 2 N; P(n).

1Where N+ denotes the positive natural numbers, i.e. N f0g.

(b) If we failed to prove (3), but kept the other two statements, what

values would we be able to conclude that P holds for? Repeat for

(2) and (1).

3. Let S be the smallest set of strings dened by:

u 2 S

if s 2 S then ys 2 S

if s 2 S then sh 2 S

if s1; s2 2 S then s1s2 2 S

Use structural induction to prove that no strings in S contain the substring

yh.

Hint: It may help to strengthen your induction hypothesis.

4. Dene A(n) as the smallest natural number containing exactly n substrings in its decimal representation which are prime numbers.

For example, A(2) = 13, because the string `13′ contains the prime numbers 3 and 13 itself (and is smaller than any other number with this

property, such as 31). A(6) = 373, corresponding to the prime numbers 3

(which appears twice), 7, 37, 73, and 373.

Prove that A(n) is dened for each n 2 N. i.e. for each n 2 N, there

exists a smallest natural number containing exactly n prime substrings.

2