CS计算机代考程序代写 CMSC 250, Fall 2021

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