Answers to Problem Set 5
Name: Neo Liu
MATH-UA 120 Discrete Mathematics
due March 24, 2023
These are to be written up in LATEX and turned in to Gradescope.
Assigned Problems
1. Prove the following statement by contrapositive:
For all n ∈ N, if 2n < n!, then n > 3.
Answer. The contrapositive statement can be written as ∀n ∈ N, if ¬(n > 3),
then ¬(2n < n!). The contrapositive statment is equal to if n ≤ 3, then 2n ≥ n!.
Since n ∈ N ∧ n ≤ 3, the only possible values of n is 0, 1, 2, 3. When n = 0,
then 20 = 1, 0! = 1. Therefore, 20 ≥ 0!. When n = 1, then 21 = 2, 1! = 1.
Therefore, 2! ≥ 1!. When n = 2, then 22 = 4, 2! = 2×1 = 2. Therefore, 22 ≥ 2!.
When n = 3, then 23 = 8, 3! = 3 × 2 × 1 = 6. Therefore, 23 ≥ 3!. Since the
contrapositive statement is logically equilvalent to the original statement, and
we shows that the contrapositive statement is true given the domain of n from
0 to 3, we can conclude that the origianl statement also holds true.
2. Prove the following by contradiction:
Let A,B,C be sets. If A ⊆ B and B ∩ C = ∅, then A ∩ C = ∅.
Answer. To prove by contradiction, we first write the negation of the state-
ment: let A, B, C be sets (define x as an element). If A ⊆ B ∧B ∪C = ∅, then
A ∩ C ̸= ∅, and shows that the negation statement is logically absurd. Since
we knows that A ⊆ B, we know ∀x ∈ A, x ∈ B. In other words, ∄x /∈ B such
that x ∈ A. The second condition of the statement that B ∩C = ∅ implies that
∀x ∈ C, x /∈ B. Since we have shown that we cannot find an element x that
does not belong to B but simultaneously belong to A, and we also know that all
element belong to C does not belong to B, we can conclude that for all element
belong to C, it does not belong to A. Therefore, the negation of the original
statement that A∩C = ∅ is absurd, and we prove the original statement is true.
1
3. Prove the following by smallest counterexample:
Let n ∈ N. If n ≥ 1, then 4 | (5n − 1).
Answer. To prove by the smallest counterexample, we first comes up with
the negation of the original statement: ∀n ∈ N, we assume ∃n ≥ 1 such that
4 ∤ (5n− 1). For n = 1, 51− 1 = 5− 1 = 4∧ 4|4, which means that n = 1, which
is at the bottom of the domain of n, is not a counterexample. So if there exists
a counterexample (a natural number), it should be greater than 1. Denote the
counterexample as k and since in order for the counterexample is greater than
1, k must be greater or equal to 1 (k − 1 ≥ 1). Substituting k - 1 into 5n − 1
and assume the original statement is true, 4|5k−1 − 1. In other words, ∃a ∈ N
such that 4a = 5k−1 − 1.
To increase the exponent of 5k−1 by 1, multiply both side of the equation
by 5 and we get 20a = 5k − 5. 20a+4 = 5k − 1. Since 20a+4 can be simplified
as 4(5a + 1), which is certainly a multiple of 4, we know that the negation of
the original statement that ∃n ≥ 1 such that 4 ∤ (5n − 1) is a contradiction and
therefore is false. So we prove that the statement is correct using the smallest
counterexample.
4. Let n ≥ 1. Suppose we want a bit pattern of length n (i.e. a sequence of
1’s and 0’s of length n such as 011001010...). Use induction to prove there are
2n−1 bit patterns with an even number of 1’s.
Answer.
Base Case: n =1; the number of pattern of 1’s is 1. Take the smallest pos-
sible n value equal to 1. Plug into 2n−1 = 21−1 = 20 = 1. The base case is
true since when the bit length is equal to 1, the only possible even number
of 1’s we can find is 0
Inductive Hypothesis: There are 2n−1 bit patterns that contains even num-
ber of bits given the bit length of n, then there are 2n bit patterns with
an even number of 1’s given n+ 1 bits.
Inductive Step: To conduct the inductive proof, select a base case and an
extreme case in which the bit length is 1 and the bit length is n. For the
sequence that has the bit length of n, there are 2n patterns since for every
single one bits, there are two disjoint probabilities that the bit is either 1
or 0. Within the mentioned bitstring, the given conditions that there are
2n−1 number of patterns that contains even numbers of 1’s, the number
of patterns that contains odd numbers of 1’s is 2n− 2n−1 = 2n−1. For the
bitstring that contains odd number of 1’s, we can add a 1 at the end; for
the bistring that contains even number of 1’s already, we can add a 0 at the
end so that the number of 1’s will stay even. In both case, the bitlength
will increase by 1; the number of patterns that contain even number of 1’s
will be 2n−1 + 2n−1 = 2n. Therefore, the statement is proved using the
induction.
2
5. Use strong induction to show if n, k ∈ N with 0 ≤ k ≤ n, and n is even and
k is odd, then
(
n
k
)
is even. Hint: Use the identity
(
n
k
)
=
(
n−1
k−1
)
+
(
n−1
k
)
.
Answer.
base case : substitute the value of n - 2 and n = 4, and k = 1 and k = 3 into
the combination
(
n
k
)
:
(2
1
)
= 2,
(4
1
)
= 4,
(4
3
)
= 4. The base case shows that
all the results are even number.
inductive hypothesis Given that the k is an odd number and n is an even
number, for all 0 ≤ k ≤ n, we get (nk) is also even. Now assuming exists
another even natural number m such that m > n and
(
m
k
)
is also even.
inductive step Given the identity
(
n
k
)
=
(
n−1
k−1
)
+
(
n−1
k
)
, this also applies to
m such that
(
m
k
)
=
(
m−1
k−1
)
+
(
m−1
k
)
.
(
m−1
k−1
)
+
(
m−1
k
)
can be further broke
down into
(
m−1−1
k−1−1
)
+
(
m−1−1
k−1
)
+
(
m−1−1
k−1
)
+
(
m−1−1
k
)
. And we get
(
m−2
k−2
)
+
2
(
m−2
k−1
)
+
(
m−2
k
)
. Given the assumption that when m is even and k is odd,
the combination will also be even, we know that both
(
m−2
k
)
and
(
m−2
k−2
)
will
be even, and 2 times any number will produce an even number, therefore,
we prove that
(
m
k
)
will be even when m is even.