CMSC 250, Fall 2021
Midterm #2
First & Last Name:
UID (9 digits):
Section number (4 digits):
University Honor Pledge:
I pledge on my honor that I have not given or received
any unauthorized assistance on this assignment/examination.
Please sign or initial below:
NOTES
• Please silence and put away all electronic devices.
• You may not use a calculator.
• Write neatly – if we cannot read your answer, you will receive no credit.
• You have 75 minutes for the exam.
• You may not leave the classroom during the last 5 minutes of the exam.
• You may assume that an Integer + Integer = Integer, and that Integer∗Integer
= Integer.
• You may assume that if x is an Integer, then it is either even or odd and it is
even iff it is not odd and hence odd iff it is not even.
• You many use only the Laws of Equivalence found in Table 1.
• You may use only the Rules of Inference found in Table 2.
• You may use only the Summation Formulas given in Table 3.
• These tables are on a page attached at the end. Remove that page now!
Your Name:
Problem 1: Proof By Contradiction [Total 10 pts]
Prove the following via a proof by contradiction:
∀a, b ∈ Z, a ≥ 2 ⇒
[
a ∤ b or a ∤ (b+ 1)
]
This is a proof via contradiction so lets assume the contradiction: ∃a, b,∈ Z, a ≥ 2∧
[
a|b∧ a|(b+1)
]
If a|b ∧ a|(b+ 1) then we know b = ak for some k ∈ Z and (b+ 1) = am for some m ∈ Z.
Thus, ak + 1 = am which means 1 = am− ak
This means 1 = ap for some p ∈ Z 1
p
is not an integer unless p is 1, but that would mean a = 1 but
a ≥ 2. This is a contradiction so we know the original statement must be true.
Problem 2: Set Proof [Total 10 pts]
Prove that for all sets A,B that A ∩ B = A − Bc (You cannot use set identities, hence we did not
give you the table).
To show set equality, we must show that A ∩B ⊆ A−Bc and A−Bc ⊆ A ∩B.
Let us start with proving A ∩B ⊆ A−Bc
If any element x ∈ A ∩B, then x ∈ A and x ∈ B
If x ∈ B then we know that x ̸∈ Bc
If x ∈ A and x ̸∈ Bc, then we know that x ∈ A−Bc. Thus A ∩B ⊆ A−Bc
Let us now prove A−Bc ⊆ A ∩B
If any element x ∈ A−BC , the x ∈ A ∧ x ̸∈ Bc
If x ̸
∫
Bc then x ∈ B
Thus if we know that x ∈ A and x ∈ B, then we know x ∈ A ∩B. Thus A−Bc ⊆ A ∩B.
Since we have proved that A ∩B ⊆ A−Bc and A−Bc ⊆ A ∩B, then we can say for all sets A,B
that A ∩B = A−Bc
Problem 3: Set Disproof [Total 5 pts]
Disprove that for all sets A,B that A−Bc ⊆ U −B, where U is the universal set.
Suppose that U = {1, 2, 3, 4}, A = {1, 2} and B = {2, 3}. This means that Bc = {1, 4}, A−Bc = {2}
and U −B = {1, 4} However we can see that 2 ∈ A−Bc, but 2 ̸∈ U −B so A−Bc is not a subset
of U −B
Problem 4: Things in Sets [Total 12 pts]
(a) Use set-builder notation to define the set of all even factors of a, where a = 100! (factorial). [4 pts]
{x ∈ Z|∃k ∈ Z, x = 2k ∧ x|100!}
(b) Explicitly list all the elements in the set:{
a ∈ Z | (a ≤ 25) ∧
(
∃b ∈ Z, a = b2 − 1
)}
[4 pts]
{-1, 0, 3, 8, 15, 24}
(c) Explicitly list all the elements in the set:
P ({∅} × {{∅}, ∅})
[4 pts]
{∅, {(∅, {∅})}, {(∅, ∅)}, {(∅, {∅}), (∅, ∅)}}
Problem 5: Countability [Total 8 pts]
Fill the corresponding circle in completely – no justification needed.
(a) {x ∈ R | 2 < x < 4} [2 pts]
Finite: ○ Countably infinite: ○ Uncountably infinite
(b) R− Z [2 pts]
Finite: ○ Countably infinite: ○ Uncountably infinite
(c) P(Q) [2 pts]
Finite: ○ Countably infinite: ○ Uncountably infinite
(d) All partitions of Z [2 pts]
Finite: ○ Countably infinite: ○ Uncountably infinite
Problem 6: Sequences [Total 20 pts]
Write the first 5 terms from each of the following sequences starting at n = 0:
(a) an = (2 + (−1)n)n, for n ≥ 0 [5 pts]
0,1,6,3,12,5,18
(b) bn =
−2 n = 0
1 n = 1
0.5bn−2 + bn−1 n ≥ 2
[5 pts]
−2, 1, 0, 0.5, 0.5
Give a non-recursive (closed-form/explicit), non-piecewise definition for the following sequences,
starting at a0:
(c) 6, 3, 12, 5, 18, 7, 24, 9, 30, 11, 36, . . . [5 pts]
an = (2 + (−1)n)(n+ 2), for n ≥ 0
This is actually just a shift from part (a)
(d) 81, 27, 9, 3, 1, 1
3
, 1
9
, . . . [5 pts]
an = 3
4−n
Problem 7: A Sum [Total 8 pts]
Compute and write the following sum without sigma notation. Do not simply write out the terms
but use the appropriate formulas to reduce this to a single numerical expression which does not need
to be simplified.
30∑
i=3
(
i− 32−i
)
30∑
i=3
(
i− 32−i
)
=
30∑
i=3
(i)−
30∑
i=3
(
32−i
)
30∑
i=3
(i) =
30∑
i=1
(i)− (1 + 2) =
30(31)
2
− 3
30∑
i=3
(
32−i
)
=
30∑
i=0
(
32−i
)
− (32 + 31 + 30) =
30∑
i=0
(
32
(
1
3
)i)
− 13 = 32
30∑
i=0
(
(
1
3
)i
)
− 13 = 9
(
1−
(
1
3
)30+1
1− 1
3
)
− 13
30∑
i=3
(i− 32−i) =
30(31)
2
− 3− 9
(
1−
(
1
3
)31
2
3
)
+ 13
Problem 8: A Nested Expression [Total 7 pts]
Compute and write the following nested expression without sigma/pi notation. Do not simply write
out the terms but use the appropriate formulas to reduce this to a single numerical expression which
does not need to be simplified.
103∏
k=100
k∑
j=1
j2
103∏
k=100
k∑
j=1
j2 =
( 100∑
j=1
j2
)( 101∑
j=1
j2
)( 102∑
j=1
j2
)( 103∑
j=1
j2
)
(
100(100+1)(2(100)+1)
6
)(
101(101+1)(2(101)+1)
6
)(
102(102+1)(2(102)+1)
6
)(
103(103+1)(2(103)+1)
6
)
Problem 9: Weak Induction [Total 10 pts]
Using Weak Induction prove that ∀n ≥ 3 we have:
n∑
i=3
4i =
4(4n − 16)
3
Let the Predicat P (x) be the statement
n∑
i=3
4i =
4(4n−16)
3
.
Base Case: We want to prove P (3) is true.
P (3) =
3∑
i=3
4i
?
=
4(43−16)
3
43
?
= 192
3
64 = 64 !
IS: The IH is the assumption that for any k > 3, P (k) is true
We want to prove that P (k + 1) is true
P (k + 1) =
k+1∑
i=3
4i
?
=
4(4k+1−16)
3
k+1∑
i=3
4i =
k∑
i=3
(4i) + 4k+1 =
4(4k−16)
3
+ 4k+1 (by IH).
4(4k−16)
3
+ 4k+1
?
=
4(4k+1−16)
3
4k+1 − 4(16) + 3(4k+1) = 4k+1(1 + 3)− 4(16) ?= 4(4k+1 − 16)
4(4k+1 − 16) = 4(4k+1 − 16) ✓
Problem 10: Challenge Question (NON-OPTIONAL) [Total 10 pts]
Prove that:
{x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8} ⊂ Zodd
Let a ∈ {x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8}. We wish to show that a ∈ Zodd.
Since a ∈ {x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8}, either a ∈ {x ∈ Z |x ≡ 3 mod 4} or a ∈
{y ∈ Z | y ≡ 1 mod 8} (or both). We proceed by cases:
• Case 1: a ∈ {x ∈ Z |x ≡ 3 mod 4}. Then a ≡ 3 mod 4. This means 4 | (a− 3), so there exists
some integer k such that a− 3 = 4k. That means a = 4k+3 = 2(2k)+2+1 = 2(2k+1)+1 =
2k′ + 1 where k′ = 2k + 1 is an integer (by closure). Thus, a is odd and so a ∈ Zodd.
• Case 2: a ∈ {y ∈ Z | y ≡ 1 mod 8}. Then a ≡ 1 mod 8. This means 8 | (a− 1), which in turn
means there exists some integer k such that a− 1 = 8k. That means a = 8k+1 = 2(4k)+ 1 =
2k′ + 1 where k′ = 4k is an integer (by closure). Thus, a is odd, meaning a ∈ Zodd.
In both cases, a ∈ Zodd. Therefore {x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8} ⊆ Zodd. In order
to show that {x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8} ⊂ Zodd (i.e., the LHS is a proper subset
of the RHS), we must show that the two sets are not equal. It suffices to show that there is some
element b ∈ Zodd such that b /∈ {x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8}.
Consider b = 5. We claim that b is odd but b /∈ {x ∈ Z |x ≡ 3 mod 4} ∪ {y ∈ Z | y ≡ 1 mod 8}.
Certainly, b = 5 = 2(2) + 1 is odd. However 5 ≡ 1 ̸≡ 3 mod 4 and thus b /∈ {x ∈ Z |x ≡ 3 mod 4}.
Further, b ≡ 5 ̸≡ 1 mod 8, and thus b /∈ {y ∈ Z | y ≡ 1 mod 8}.
Tables!
Commutative Laws p ∧ q ≡ q ∧ p p ∨ q ≡ q ∨ p
Associative Laws (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive Laws p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Identity Laws p ∧ t ≡ p p ∨ c ≡ p
Negation Laws p ∨ ∼p ≡ t p ∧ ∼p ≡ c
Double Negation Law ∼(∼p) ≡ p
Idempotent Laws p ∧ p ≡ p p ∨ p ≡ p
Universal Bound Laws p ∨ t ≡ t p ∧ c ≡ c
DeMorgan’s Laws ∼(p ∧ q) ≡ ∼p ∨ ∼q ∼(p ∨ q) ≡ ∼p ∧ ∼q
Absorption Laws p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p
Negation Laws of t and c ∼t ≡ c ∼c ≡ t
Definition of Implication p ⇒ q ≡ ∼p ∨ q
Definition of Biconditional p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) ≡ (p ∧ q) ∨ (∼p ∧ ∼q)
Contrapositive p ⇒ q ≡ ∼q ⇒ ∼p
Table 1: Laws of Equivalence
Modus Ponens Modus Tollens Generalization
p ⇒ q
p
∴ q
p ⇒ q
∼q
∴ ∼p
p
∴ p ∨ q
Specialization Conjunction Elimination
p ∧ q
∴ p
p
q
∴ p ∧ q
p ∨ q
∼p
∴ q
Transitivity Cases Contradiction
p ⇒ q
q ⇒ r
∴ p ⇒ r
p ∨ q
p ⇒ r
q ⇒ r
∴ r
∼p ⇒ c
∴ p
Table 2: Rules of Inference
n∑
i=1
1 = n Sum of 1
n∑
i=1
i =
n(n+1)
2
Gauss’ Sum
n∑
i=1
i2 =
(n)(n+1)(2n+1)
6
Sum of Squares
n∑
i=0
ri = 1−r
n+1
1−r Geometric Sum
Table 3: Allowed Summation Formulas