Questions: Proof Strategies in Discrete Mathematics

Question 1

To prove 'if n² is even, then n is even,' which proof strategy is most natural and why?

• A. Direct proof — assume n² is even and algebraically derive that n must be even
• B. Proof by contrapositive — prove the equivalent 'if n is odd, then n² is odd'
• C. Proof by induction — prove the base case n = 0, then show the inductive step holds
• D. Proof by cases — consider all possible values of n mod 4

Answer: (B)

The contrapositive 'if n is odd then n² is odd' is far easier to prove directly: write n = 2k+1, compute n² = 4k²+4k+1 = 2(2k²+2k)+1, which is odd. Attempting a direct proof of the original requires extracting structure from 'n² is even' to conclude something about n — harder algebraically. The contrapositive is logically equivalent (proving ¬Q → ¬P proves P → Q), so it's the same result with a cleaner path.

Question 2

A student wants to prove √3 is irrational. They write: 'Assume √3 = p/q in lowest terms.' They derive that p must be divisible by 3, then that q must be divisible by 3, contradicting 'lowest terms.' What proof strategy are they using, and what exactly did they assume?

• A. Proof by contrapositive — they proved that rationality implies a divisibility property
• B. Proof by contradiction — they assumed the negation of the entire conclusion ('√3 is rational') and derived a logical impossibility
• C. Direct proof — they assumed the hypothesis and derived the conclusion through algebra
• D. Proof by contradiction — they assumed the negation of an intermediate step, not the full conclusion

Answer: (B)

This is proof by contradiction. The goal is '√3 is irrational,' so the student assumes its negation: '√3 is rational,' represented as p/q in lowest terms. Deriving that both p and q are divisible by 3 contradicts the lowest-terms assumption. Option D names a common error: assuming the negation of an intermediate claim rather than the whole goal statement. In a correct contradiction proof, you always negate the entire conclusion.

Question 3

In a proof by mathematical induction, the inductive hypothesis is assumed true for an arbitrary value k and then used as a tool to prove the statement holds for k+1.

• T. True
• F. False

Answer: True

This is the defining structure of the inductive step. You do not prove the inductive hypothesis — you assume it for an arbitrary k and use it as a licensed premise to establish the k+1 case. The chain: base case holds → inductive step shows k implies k+1 for every k → by the induction principle, the statement holds for all natural numbers. The conditional assumption is not circular; it is the mechanism that makes the chain of dominoes work.

Question 4

Proof by contrapositive and proof by contradiction are essentially the same strategy because both require negating something.

• T. True
• F. False

Answer: False

They differ in structure and scope. Contrapositive: to prove P → Q, directly prove ¬Q → ¬P — assume ¬Q, derive ¬P, done. No contradiction is needed; the proof ends at a conclusion. Contradiction: assume both P and ¬Q simultaneously, then derive any logical impossibility (False). Contradiction is more open-ended and can prove non-conditional statements ('√2 is irrational'). Contrapositive is cleaner when available because it is just a direct proof of an equivalent statement — the negation provides a concrete starting point rather than an explosive search for inconsistency.

Question 5

Explain the difference between proof by contrapositive and proof by contradiction. When is contrapositive preferred over contradiction?

Model answer: Contrapositive: to prove P → Q, prove ¬Q → ¬P (logically equivalent). Assume ¬Q, derive ¬P — the proof ends when you reach that conclusion. Contradiction: assume P ∧ ¬Q and derive any impossibility. Contrapositive is preferred when ¬Q (the negation of the conclusion) gives a useful algebraic or structural foothold that makes the derivation clean and direct. Contradiction is preferred when the goal is not a conditional, or when combining P and ¬Q naturally produces a collision between two incompatible claims.

A reliable indicator for contrapositive: look at P → Q and ask whether ¬Q is more concrete or workable than P. If yes, flip it. Contradiction is the fallback when neither direction is straightforwardly usable, or when the goal statement itself is not a conditional.