Description
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