TMUA Proof Techniques 4 — Questions and Answers
Question 1: Which of the following is NOT a valid method of mathematical proof?
- Proof by contrapositive
- Proof by induction
- Proof by example (Correct answer)
- Proof by contradiction
Correct answer: Proof by example
A single example proves existence but cannot prove a universal statement; only a counterexample can disprove one.
Question 2: To prove ∑_{k=1}^{n} k = n(n+1)/2 by induction, the base case checks:
- n = 0: 0 = 0(1)/2 ✓
- n = 1: 1 = 1(2)/2 ✓ (Correct answer)
- n = 2: 3 = 2(3)/2 ✓
- Both n=0 and n=1
Correct answer: n = 1: 1 = 1(2)/2 ✓
The standard base case is n = 1: the left side is 1 and the right side is 1(2)/2 = 1, which checks out.
Question 3: If a proof assumes 'let n be an arbitrary even integer' and derives a property, the conclusion holds for:
- Only the specific n chosen
- All even integers (Correct answer)
- All integers
- All positive integers
Correct answer: All even integers
Proving a property for an arbitrary even integer, with no further assumptions, establishes it universally for all even integers.
Question 4: A proof shows: 'Assume for contradiction that there are finitely many primes p₁, p₂, …, pₙ. Consider N = p₁p₂⋯pₙ + 1.' The next key observation is:
- N is prime
- N is divisible by some pᵢ
- N has a prime factor not in the list (Correct answer)
- N is even
Correct answer: N has a prime factor not in the list
N leaves remainder 1 when divided by any pᵢ, so its prime factors are not in the assumed complete list — a contradiction.
Question 5: What is the logical form of modus tollens?
- P, P ⇒ Q ⊢ Q
- ¬Q, P ⇒ Q ⊢ ¬P (Correct answer)
- P ⇒ Q, Q ⇒ R ⊢ P ⇒ R
- ¬P ⊢ ¬(P ∧ Q)
Correct answer: ¬Q, P ⇒ Q ⊢ ¬P
Modus tollens: given P ⇒ Q and ¬Q, we conclude ¬P — the basis of many proof by contradiction arguments.
Question 6: When proving 'there are infinitely many odd numbers', the most direct approach is:
- Proof by induction showing 2n−1 is odd for all n ∈ ℕ (Correct answer)
- Proof by contradiction assuming finitely many
- Proof by exhaustion
- Proof by contrapositive
Correct answer: Proof by induction showing 2n−1 is odd for all n ∈ ℕ
Showing the formula 2n−1 is odd for every positive integer n directly exhibits infinitely many odd numbers.
Question 7: In a proof by induction on a statement about divisibility, the inductive step typically uses:
- A new application of the base case
- The inductive hypothesis to rewrite the (k+1)-th expression in terms of the k-th (Correct answer)
- A separate proof by contradiction
- Proof by contrapositive on the k-th case
Correct answer: The inductive hypothesis to rewrite the (k+1)-th expression in terms of the k-th
The inductive hypothesis P(k) is substituted into the expression for P(k+1) to complete the divisibility argument.
TMUA Proof Techniques 4
Which of the following is NOT a valid method of mathematical proof?