CSC/MAT A67 Proof Assignment 2 Winter 2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSC/MAT A67
Proof Assignment 2
Winter 2023
♦ Due: February 10 at 11:59pm.
This assignment is meant to help you learn how to write induction proofs in this course — and possibly for the rest of your life.
1. Here is a proof which is taken from class. It uses Principle of Mathematical Induction (PMI) to prove that 2n < n! for every integer n ≥ 4.
Let P (n) be the proposition 2n < n!.
We use PMI to prove that P (n) is true for every integer n ≥ 4.
Basis Step:
P (4) is the statement 24 < 4!.
This is true because 24 = 16 < 24 = 4!.
Induction Step:
For IH, let k ≥ 4 be an arbitrary integer and assume that 2k < k!.
WTS: 2k+1 < (k + 1)!.
2k+1
= 2k · 2
< k! · 2 [by IH]
< k! · (k + 1) [since 2 < k + 1]
= (k + 1)!
as wanted.
Therefore, by PMI, 2n < n! for all integers n ≥ 4.
With the above proof as a model, use PMI to prove that 3n < n! for every integer n ≥ 7.
2. Here is a proof by Principle of Complete Induction (PCI, also called strong induction), which is taken from class. It proves that f (n) < 2n for all nonnegative integers n, where f (n) is deined by
f (n) = {2(n)f (n 3) + 3f (n 2)
if 0 
n 
2;
if n > 2.
We use PCI to prove that f (n) < 2n for all nonnegative integers n.
Basis Step:
We consider 3 cases: n = 0, n = 1, n = 2.
If n = 0, then f (n) = 0 [by deinition of f] and 2n = 1.
So f (0) < 20 .
If n = 1, then f (n) = 1 [by deinition of f] and 2n = 2.
So f (1) < 21 .
If n = 2, then f (n) = 2 [by deinition of f] and 2n = 4.
So f (2) < 22 .
Induction Step:
For IH, let k > 2 be an arbitrary integer and assume that
f (j) < 2j for all integers j where 0 
j < k .
WTS: f (k) < 2k .
f (k)
= 2f (k 3) + 3f (k 
2) [by deinition of f ; k > 2]
< 2 · 2k —3 + 3 · 2k —2 [by IH (twice); 0 
k 
3 < k 
2 < k]
= (1 + 3) · 2k —2 [factor out 2k —2]
= 4 · 2k —2
= 2k
as wanted.
Therefore, by PCI, f (n) < 2n for all nonnegative integers n.
We deine a function g that maps positive integers to nonnegative integers as follows.
0 if n = 1;
3 if n = 2;
g(n) =〈 8 if n = 3;
15 if n = 4;
‘ (g(n 4) + g(n 
1) + 10n 
17)/2 if n > 4.
With the above proof as a model, use PCI to prove that g(n) < n2 for every positive integer n.
2023-02-13