TMUA Proof Techniques 2 — Questions and Answers
Question 1: Which method proves a statement by assuming the negation of the conclusion and deriving a contradiction?
- Proof by induction
- Proof by contrapositive
- Proof by contradiction (Correct answer)
- Proof by exhaustion
Correct answer: Proof by contradiction
Proof by contradiction assumes the negation is true and shows this leads to a logical impossibility.
Question 2: To prove P ⇒ Q by contrapositive, what do you actually prove?
- Q ⇒ P
- ¬P ⇒ ¬Q
- ¬Q ⇒ ¬P (Correct answer)
- ¬P ⇒ Q
Correct answer: ¬Q ⇒ ¬P
The contrapositive of P ⇒ Q is ¬Q ⇒ ¬P, which is logically equivalent to the original statement.
Question 3: In a proof by induction, the inductive step proves which of the following?
- P(1) is true
- P(k) is true for all k
- P(k) ⇒ P(k+1) (Correct answer)
- P(n) is true for n=0
Correct answer: P(k) ⇒ P(k+1)
The inductive step assumes P(k) (the inductive hypothesis) and deduces P(k+1).
Question 4: Which of the following is a valid counterexample to the claim 'All prime numbers are odd'?
- 3
- 7
- 2 (Correct answer)
- 11
Correct answer: 2
2 is prime and even, disproving the claim that all primes are odd.
Question 5: A proof that every integer n satisfies n² ≥ 0 is best classified as:
- Proof by contradiction
- Proof by cases
- Direct proof using algebraic identity (Correct answer)
- Proof by induction
Correct answer: Direct proof using algebraic identity
Writing n² = (n)(n) and noting a product of two numbers with the same sign is non-negative is a direct algebraic proof.
Question 6: When proving 'there exists an irrational number x such that x² is rational', which approach works?
- Universal proof covering all irrationals
- Proof by induction on the integers
- Constructive existence proof giving a specific example (Correct answer)
- Proof by contradiction only
Correct answer: Constructive existence proof giving a specific example
Taking x = √2 gives x² = 2, which is rational — a constructive existence proof.
Question 7: In strong induction, the inductive hypothesis assumes:
- Only P(k) is true
- P(1) and P(2) are true
- P(j) is true for all j ≤ k (Correct answer)
- P(k+1) is true
Correct answer: P(j) is true for all j ≤ k
Strong induction assumes the statement holds for all integers up to k, not just for k alone.
TMUA Proof Techniques 2
Which method proves a statement by assuming the negation of the conclusion and deriving a contradiction?