Proof Techniques Flashcards

Prove: if n² is even then n is even. The most efficient technique is:

Answer: Proof by contrapositive

Contrapositive: if n is odd then n² is odd, which follows immediately from (2k+1)² = 4k²+4k+1.

Which of the following correctly states the well-ordering principle used in many proofs?

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.

To prove ∀n ∈ ℕ, n(n+1) is even, a direct proof uses:

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.

Which logical equivalence justifies replacing a proof of P ⇒ Q with a proof of ¬Q ⇒ ¬P?

Answer: Contrapositive equivalence

The contrapositive P ⇒ Q ≡ ¬Q ⇒ ¬P is a tautology, so both statements have identical truth values.

A proof by exhaustion is appropriate when:

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.

Which statement about 'if and only if' (iff) proofs is correct?

Answer: Both P ⇒ Q and Q ⇒ P must be proved separately

An iff proof requires establishing both implications: P ⇒ Q and Q ⇒ P.

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:

Answer: p is divisible by 3

3 | p² implies 3 | p (since 3 is prime), so p = 3k for some integer k.