Discrete Computational Structures Assignment #7

CS 230 : Discrete Computational Structures

Assignment #7

Suggested Reading: Rosen Section 5.1 - 5.2; Lehman et al. Chapter 5.1 - 5.3
These are the problems that you need to turn in. For more practice, you are encouraged to
work on the other problems. Always explain your answers and show your reasoning.
For Problems 1-4 and 6, prove the statements by mathematical induction. Clearly state your
basis step and prove it. What is your inductive hypothesis? Prove the inductive step and show
clearly where you used the inductive hypothesis.
1. [5 Pts] n + 3 < 5n
2
, for all positive integers n.
(a) Base case: (1) + 3 < 5(1)2
, 4 < 5
(b) Induction Hypothesis: Assume k + 3 < 5k
2
(c) Prove (k + 1) + 3 < 5(k + 1)2
(d) (k + 3) + 1 < 5k
2 + 10k + 5
(e) by IH, (k + 3 < 5k
2
). It now follows that we should prove 1 < 10k + 5
(f) 1 < 10k + 5 because 1 is always less than 5, regardless of positive k.
(g) Therefore, (k + 3) + 1 < 5k
2 + 10k + 5; QED.
2. [5 Pts] 1 · 1! + 2 · 2! + · · · + n · n! = (n + 1)! − 1, for all positive integers n.
(a) Base case: (1) ∗ (1)! = ((1) + 1)! − 1 = 1
(b) Induction Hypothesis: Assume 1 ∗ 1! + 2 ∗ 2! + ... + k ∗ k! = (k + 1)! − 1, 1 ∗ 1! + 2 ∗ 2! +
... + k ∗ k! + 1 = (k + 1)!
(c) Prove 1 ∗ 1! + 2 ∗ 2! + ... + (k + 1) ∗ (k + 1)! = (k + 1) + 1)! − 1
(d) 1 ∗ 1! + 2 ∗ 2! + ... + k ∗ k! + (k + 1) ∗ (k + 1)! = (k + 2)! − 1
(e) 1 ∗ 1! + 2 ∗ 2! + ... + k ∗ k! + (k + 1) ∗ (k + 1)! = (k + 1)!(k + 2) − 1
(f) 1 ∗ 1! + 2 ∗ 2! + ... + k ∗ k! + 1 + (k + 1) ∗ (k + 1)! = (k + 1)!(k + 2)
(g) By IH, (k + 1)! + (k + 1) ∗ (k + 1)! = (k + 1)!(k + 2)
(h) Dividing both sides by (k + 1)!: 1 + (k + 1) ∗ 1 = 1 ∗ (k + 2)
(i) Collecting terms, k + 2 = k + 2; QED
3. [5 Pts] 1
1·2 +
1
2·3 + · · · +
1
n·(n+1) =
n
n+1 , for all positive integers n.
(a) Base case: 1
(1)·(1+1) =
(1)
(1)+1 =
1
2
(b) Induction Hypothesis: Assume 1
1·2 +
1
2·3 + · · · +
1
k·(k+1) =
k
k+1
(c) Prove 1
1·2 +
1
2·3 + · · · +
1
k·(k+1) +
1
(k+1)·((k+1)+1) =
(k+1)
(k+1)+1
(d) 1
1·2 +
1
2·3 + · · · +
1
k·(k+1) +
1
(k+1)·(k+2) =
k+1
k+2
(e) By IH, k
k+1 +
1
(k+1)·(k+2) =
k+1
k+2
(f) k(k+2)
(k+1)(k+2) +
1
(k+1)·(k+2) =
k+1
k+2
(g) k
2+2k+1
(k+1)(k+2) =
k+1
k+2
(h) (k+1)(k+1)
(k+1)(k+2) =
k+1
k+2
(i) k+1
k+2 =
k+1
k+2 ; QED
4. [5 Pts] 15 divides 42n − 1, for all natural numbers n.
(a) Base case: 4
2(1)−1
15 = 1
(b) Induction Hypothesis: 4
2k−1
15 = A, 42k = 15A + 1, A ∈ N
(c) Prove 4
2(k+1)−1
15 = B, B ∈ N
(d) 42k+2 = 15B + 1
(e) 42 ∗ 4
2k = 15B + 1
(f) By IH, 42 ∗ (15A + 1) = 15B + 1
(g) 16 ∗ (15A + 1) = 15B + 1
(h) 16 ∗ 15A + 16 = 15B + 1
(i) 16 ∗ 15A = 15B − 15
(j) 16A = B − 1
(k) B = 16A + 1
(l) Since A ∈ N, B = 16A + 1 ∈ N; QED
5. [9 Pts] Let P(n) be the statement that n-cent postage can be formed using just 4-cent and
7-cent stamps. Prove that P(n) is true for all n ≥ 18, using the steps below.
(a) First, prove P(n) by regular induction. State your basis step and inductive step clearly
and prove them.
i. Base Case: P(18), 18 = 4 + (2)7
ii. Inductive Hypothesis: k ≥ 18 can be made by some linear combination of 4 and 7
iii. Prove k + 1 can be made by some linear combination of 4 and 7
iv. CASE 1: Atleast 1 7 is used. Replace a 7 with 2 4’s, k − 7 + 2(4) = k + 1
v. CASE 2: No 7’s, k = 4a, a ∈ N. Since k ≥ 18, 4a ≥ 20, a ≥ 5. Atleast 5 4’s.
Replace 5 4’s with 3 7’s. k − (5)4 + (3)7 = k + 1
QED
(b) Now, prove P(n) by strong induction. Again, state and prove your basis step and
inductive step. Your basis step should have multiple cases.
i. Base Cases: P(18), 18 = 4 + (2)7; P(19), 19 = (3)4 + 7, P(20), 20 = (5)4, P(21),
21 = (3)7
ii. Inductive Hypothesis: Let k ≥ 21. Assume all l where 18 ≤ l ≤ k can be formed
using 4 and 7.
iii. Prove k + 1 can be formed.
iv. Since k ≥ 21, k − 3 ≥ 18, so k − 3 is possible by IH
v. k − 3 + (1)4 = k + 1.
QED
6. [6 Pts] Use mathematical induction to prove that DeMorgan’s Law holds for the intersection
of n sets, n ∈ Z+:
 \n
i=1
Ai
!
=
[n
i=1
Ai
You may use DeMorgan’s Law for two sets.
(a) Base Case: A1 ∩ A2 ∩ A3
i. A1 ∩ (A2 ∩ A3) Intersection is Associative
ii. A1 ∪ A2 ∩ A3) De Morgan’s for Two Sets
iii. A1 ∪ A3 ∪ A3 De Morgan’s for Two Sets
QED
(b) Induction Hypothesis: A1 ∩ A2 ∩ ... ∩ Ak = A1 ∪ A2 ∪ ... ∪ Ak
(c) Prove: A1 ∩ A2 ∩ ... ∩ Ak ∩ Ak+1 = A1 ∪ A2 ∪ ... ∪ Ak ∪ Ak+1
i. (A1 ∩ A2 ∩ ... ∩ Ak) ∩ Ak+1 Intersection is Associative
ii. A1 ∩ A2 ∩ ... ∩ Ak ∪ Ak+1 De Morgan’s for Two Sets
iii. A1 ∪ A2 ∪ ... ∪ Ak ∪ Ak+1 By IH
QED
For more practice, you are encouraged to work on other problems in Rosen Sections 5.1 and
5.2, like the ones below.
1. Rosen Section 5.1 Problem 4
2. Rosen Section 5.1 Problem 12
3. Rosen Section 5.1 Problem 31
4. Rosen Section 5.2 Problem 26