TMUA Proof Techniques 3 — Questions and Answers
Question 1: Prove: if n² is even then n is even. The most efficient technique is:
- Direct proof
- Proof by exhaustion
- Proof by contrapositive (Correct answer)
- Proof by construction
Correct answer: Proof by contrapositive
Contrapositive: if n is odd then n² is odd, which follows immediately from (2k+1)² = 4k²+4k+1.
Question 2: Which of the following correctly states the well-ordering principle used in many proofs?
- Every set of integers has a minimum
- Every non-empty set of positive integers has a smallest element (Correct answer)
- Every integer has a prime factorization
- Every bounded sequence converges
Correct answer: Every non-empty set of positive integers has a smallest element
The well-ordering principle states every non-empty subset of the positive integers contains a least element.
Question 3: To prove ∀n ∈ ℕ, n(n+1) is even, a direct proof uses:
- n and n+1 are both even
- n and n+1 are consecutive so one must be even (Correct answer)
- n(n+1) ≡ 0 (mod 3)
- Induction on n only
Correct answer: n and n+1 are consecutive so one must be even
Among any two consecutive integers n and n+1, exactly one is even, so their product is divisible by 2.
Question 4: Which logical equivalence justifies replacing a proof of P ⇒ Q with a proof of ¬Q ⇒ ¬P?
- De Morgan's law
- Double negation
- Contrapositive equivalence (Correct answer)
- Modus ponens
Correct answer: Contrapositive equivalence
The contrapositive P ⇒ Q ≡ ¬Q ⇒ ¬P is a tautology, so both statements have identical truth values.
Question 5: A proof by exhaustion is appropriate when:
- The domain is infinite but well-ordered
- The domain is finite and all cases can be checked (Correct answer)
- A single general argument applies to all cases
- The negation leads to a contradiction
Correct answer: The domain is finite and all cases can be checked
Proof by exhaustion works by verifying the statement for every element in a finite domain.
Question 6: Which statement about 'if and only if' (iff) proofs is correct?
- Only one direction needs to be proved
- Both P ⇒ Q and Q ⇒ P must be proved separately (Correct answer)
- It suffices to find one example where both hold
- The contrapositive proves both directions simultaneously
Correct answer: Both P ⇒ Q and Q ⇒ P must be proved separately
An iff proof requires establishing both implications: P ⇒ Q and Q ⇒ P.
Question 7: In a proof by contradiction that √3 is irrational, after assuming √3 = p/q in lowest terms and squaring, one deduces 3q² = p². This implies:
- q is divisible by 3
- p is divisible by 3 (Correct answer)
- p and q are both odd
- p² is divisible by 9 immediately
Correct answer: p is divisible by 3
3 | p² implies 3 | p (since 3 is prime), so p = 3k for some integer k.
TMUA Proof Techniques 3
Prove: if n² is even then n is even.
The most efficient technique is: