Assignment #1: induction

CSC236 
Assignment #1: induction

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 speci ed. 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 di erent 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. De ne 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 de ned 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. De ne 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 de ned for each n 2 N. i.e. for each n 2 N, there
exists a smallest natural number containing exactly n prime substrings.
2