Scribd
Upload
11 views9 pages

Discrete Math Problem Set 5 Solutions

Uploaded by

louxiaoxiao42
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views9 pages

Discrete Math Problem Set 5 Solutions

Uploaded by

louxiaoxiao42
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MATH-UA 120 Discrete Mathematics:

Problem Set 5
Jane Marple
Due Monday, October 28th, 2024

Assignment Instructions
• These are to be written up in LATEX and turned in on Gradescope.
• Click here to duplicate this .tex file in Overleaf .
• Write your solutions inside the solution environment.
• You are always encouraged to talk problems through with your peers and your instructor, but your
write up should be done independently.

• Problems are graded on correctness and fluency.


• Unless stated otherwise, all calculations require justification.
• Some tutorials on how to use LATEX can be found here. If you have any questions about LATEX
commands you can always ask your instructor for advice.

Statement on generative AI
In this and other mathematics courses, you are expected to construct clear and concise mathematical argu-
ments based on statements proven in our text and class notes. Large language models such as ChatGPT
are unable to produce this kind of solution. They also frequently generate circular logic and outright false
results.
You may use AI to summarise content, generate study plans, create problems, or do other study-related
activities. You may not ask a chatbot to solve your quiz or homework problems, or do any assessment-related
activities.
You may use AI tools to edit your grammar and punctuation, but remember that mathematical English
is not the same as academic English in other disciplines.

1
Problem 1
Prove the following statement by contrapositive: For all n ∈ N, if 2n < n!, then n > 3.

The proposition to be proved in the question is ∀n ∈ N2n < n! → n > 3. We prove the contrapositive
of the statement. ∀n ∈ Nn ≤ 3 → 2n ≥ n!. This is simple. If n = 0 then 20 = 1 ≥ 0! = 1. If n = 1,
then 21 = 2 ≥ 1! = 1. If n = 2, then 22 = 4 ≥ 2! = [Link] n = 3, then 23 = 8 ≥ 3! = 6. Therefore
∀n ∈ Nn ≤ 3 → 2n ≥ n!.

2
Problem 2

Prove the following statement by contrapositive: For all a, b ∈ Z, if a2 b2 − 2b is odd, then a and b are odd.

We prove the contrapositive of the statement, (a is even) ∨ (b is even) → a2 (b2 − 2b) is even.
There are 3 situations.
1. Suppose that a is even and b is odd. Then there exist an integer x such that a = 2x. Then

a2 (b2 − 2b) = 4x2 (b2 − 2b) = 2 · 2x2 (b2 − 2b).

Therefore a2 (b2 − 2b) is even.


2. Suppose that a is odd and b is even. Then there exist an integer x such that b = 2x. Then

a2 (b2 − 2b) = a2 (4x2 − 4x) = 2 · a2 (2x2 − 2x).

Therefore a2 (b2 − 2b) is even.


3. Suppose that a, b are both even. Then there exist two integers x such that a = 2x, b = 2y. Then

a2 (b2 − 2b) = 4x2 (4y 2 − 4y) = 2 · 2x2 (4y 2 − 2y).

Therefore a2 (b2 − 2b) is even.


It is true that (a is even) ∨ (b is even) , then a2 (b2 − 2b) is even.

3
Problem 3
Prove the following statement by contradiction: Let A, B and C be sets. If A ⊆ B and B ∩ C = ∅, then
A ∩ C = ∅.

To prove if A ⊆ B and B ∩ C = ∅, then A ∩ C = ∅ by contradiction. We assume A ⊆ B and B ∩ C = ∅


is true. and A ∩ C = ∅ is false. Then A ∩ C ̸= ∅, we also know A ⊆ B thus ∅ ̸= A ∩ C ⊆ B ∩ C. This is a
contradiction. Therefore while A ⊆ B and B ∩ C = ∅ is true, B ∩ C = ∅ must be true.

4
Problem 4
Prove the following statement by contradiction: Let x, y ∈ Z. Then x2 − 4y − 3 ̸= 0.

To prove this statement by contradiction, we assume that ∀x, y ∈ Z, x2 − 4y − 3 = 0. Thus x2 = 4y + 3,


but this is impossible for y < 0. Thus ∀x, y ∈ Z, x2 − 4y − 3 ̸= 0.

5
Problem 5
Prove the following statement by smallest counterexample: Let n ∈ N. If n ≥ 1, then 4 | (5n − 1).

Assume that the smallest integer for which this proposition does not hold is n = k (the proposition holds
for n = 1, so k must be greater than 1). Therefore, k − 1 would satisfy the proposition. Using the following
transformation:

5k − 1 = 5k − 5k−1 + 5k−1 − 1 = 5k−1 (5 − 1) + 5k−1 − 1 = 4 · 5k−1 + 5k−1 − 1

Because 4 | 5k−1 − 1, we can see that 4 | 5k − 1. This leads to a contradiction. Thus, the proposition we
wanted to prove is true.

6
Problem 6
The following is a “proof” of a false claim.
Claim (false). Let n ∈ N. Then

2n = 0. (1)

Proof. We prove the claim using proof by contradiction.


For the sake of contradiction, suppose there exists a natural number such that (1) does not hold. By the
Well-Ordering Principle, there exists a smallest x ∈ N such that 2x ̸= 0. Note that x ̸= 0. Then there exist
i, j ∈ N such that i, j < x and i + j = x. Since i, j < x we know 2i = 0 and 2j = 0. Observe

2x = 2 (i + j)
= 2i + 2j
= 0.

This contradicts the assumption that x is a counterexample to (1). Therefore, (1) holds for all n ∈ N.
Find the logic error in this proof. That is, find the the part of the proof that does not follow and allows
for the false contradiction. Do not say “the proof is wrong because the claim is false”.

He claims that for natural number x ̸= 0, there must exist two natural numbers i and j that are less
than x such that x = i + j. However, this statement is incorrect because, for x = 1, there do not exist such
integers. The smallest natural number for which the proposition does not hold is exactly x = 1.

7
Problem 7
 
2n
Let n ∈ N. Use induction to prove that < 22n−2 for all n ≥ 5.
n

First, verify the proposition for n = 5:


   
10 10! 2·5−2 10
= = 252, 2 = 256 → < 22·5−2 = 256.
5 5!5! 5

Secondly, assume that the proposition holds for n = k:


   
2n 2k
= < 22n−2 = 22k−2 .
n k

We will prove that it also holds for n = k + 1:


   
2n 2k + 2
= < 22n−2 = 22k .
n k+1

Transform the expression:


     
2k + 2 (2k + 2)! (2k + 2)(2k + 1) 2k 2k
= = <4· .
k+1 (k + 1)!(k + 1)! (k + 1)(k + 1) k k

Using the inequality for n = k, we get:


   
2k + 2 2k
<4· < 4 · 22k−2 = 22(k+1)−2 .
k+1 k
2n
 2n−2
Let A = {n ∈ N : n < 2 }. Then 5 ∈ A and k ∈ A → k + 1 ∈ A, thus A = {n ∈ N : n ≥ 5}.
2n 2n−2
Therefore, <2 for all n ≥ 5.
n

8
Problem 8

Let n ∈ Z. Use induction to prove that 3 | n3 + 2n .
Note: we want to prove the xlaim for all integers, not just natural numbers.

For n = 0, it is always true that 3 | (n3 + 2n) = 0.


Assume that for n = k, the statement holds:

3 | n3 + 2n = k 3 + 2k.

Then, from the following equations:

(k + 1)3 + 2(k + 1) = k 3 + 2k + 3(k 2 + k + 1)


(k − 1)3 + 2(k − 1) = k 3 + 2k + 3(−k 2 + k − 1),

it follows that:
3 | (k + 1)3 + 2(k + 1) and 3 | (k − 1)3 + 2(k − 1).
Let A = {n ∈ Z : 3 | (n3 + 2n)}, then 0 ∈ A and k ∈ A → k + 1 ∈ A,k ∈ A → k − 1 ∈ A thus A = Z.
Therefore, ∀n ∈ Z, 3 | (n3 + 2n).

Common questions

Powered by AI

The proof by contradiction assumes that A ∩ C has non-empty intersections despite A ⊆ B and B ∩ C = ∅ . The basis of set theory ensures that if A intersects C, then those elements are inherently in B ∩ C by the transitive nature of subsets. Since B ∩ C is explicitly empty, this assumption contradicts the primary properties of intersections, proving that A ∩ C must indeed be empty .

The logical implication holds because multiplying by an even number results in an even product. If either a or b is even, then: 1. If a is even and b is odd, a² is even, multiplying any integer by an even number results in even . 2. If a is odd and b is even, b²−2b becomes a factor of a multiple of an even basis, thus resulting in an even product . 3. If both a and b are even, a² and b²−2b are even, further ensuring the product is even . Therefore, in all cases, a²(b²−2b) is even.

The proof assumes that there exists a pair (x, y) such that x²−4y−3 = 0, which simplifies to x² = 4y + 3. It argues that y < 0 is impossible for this equation to hold as x² cannot equal a non-positive integer plus 3 . This premise forms a contradiction when assuming equality, supporting the initial negation that no integers x and y satisfy x²−4y−3 = 0.

Discussing mathematical problems with peers facilitates a deeper understanding by exposing students to different problem-solving approaches and ideas. It also encourages active learning and critical thinking as students justify solutions and scrutinize error possibilities together. Moreover, collaborative learning helps solidify knowledge through verbalization and debate, ultimately enriching individual comprehension and fluency in problem-solving .

LaTeX is essential for writing mathematical solutions due to its capabilities for producing clean, professional quality typesetting of complex mathematical expressions. It ensures consistency and readability in documentation, which is crucial for academic and professional dissemination of material. Moreover, learning LaTeX standardizes the method of presenting mathematical arguments, thus enhancing fluency and accuracy in communication .

Understanding mathematical English is crucial because the syntactic and terminological nuances in mathematical language differ from those in general academic writing. Mathematical English involves specific logical constructs, notations, and order of arguments that AI tools may misinterpret, leading to incorrect editing or unclear expressions of ideas. Therefore, proficient comprehension is necessary to ensure precise adjustments by AI .

To prove this statement by contrapositive, we need to show that for all natural numbers n, if n ≤ 3, then 2n ≥ n!. The proof involves evaluating values for n = 0, 1, 2, and 3: - For n = 0: 2^0 = 1 ≥ 0! = 1 . - For n = 1: 2^1 = 2 ≥ 1! = 1 . - For n = 2: 2^2 = 4 ≥ 2! = 2 . - For n = 3: 2^3 = 8 ≥ 3! = 6 . These calculations demonstrate that indeed, the contrapositive holds for all n ≤ 3.

The inductive proof begins by verifying the base case for n=0, such that 3 divides n³ + 2n = 0 . For the inductive step, assume it holds for n=k, i.e., 3 | k³ + 2k. Then, for n=k+1: (k+1)³ + 2(k+1) simplifies to k³ + 2k + 3(k²+k+1). Since 3 divides 3(k²+k+1) and the initial assumption holds for k³ + 2k, it follows that the divisibility continues, proving the proposition for all integers n.

Assume that there is a smallest integer k for which 5^k−1 is not divisible by 4. The proposition holds for n=1, so k must be greater than 1. For k−1, this holds i.e., 4 | 5^(k−1)−1 . From the transformation: 5^k−1 = 5·5^(k−1)−1 = (4+1)·5^(k−1)−1 = 4·5^(k−1) + 5^(k−1)−1 . Because the term 5^(k−1)−1 is divisible by 4, it leads to a contradiction that the proposition does not hold for k, proving the initial proposition.

The false proof claims that for any natural number x not equal to zero, there exist two natural numbers i and j, both less than x, such that i + j = x. However, this assumption fails for x = 1 because there are no positive integers i and j that satisfy i < 1 and j < 1 while also i + j = 1 . This incorrect assumption about the decomposability of x invalidates the supposed contradiction.

You might also like