Proof Techniques Flashcards

Which method proves a statement by assuming the negation of the conclusion and deriving a contradiction?

Answer: Proof by contradiction

Proof by contradiction assumes the negation is true and shows this leads to a logical impossibility.

To prove P ⇒ Q by contrapositive, what do you actually prove?

Answer: ¬Q ⇒ ¬P

The contrapositive of P ⇒ Q is ¬Q ⇒ ¬P, which is logically equivalent to the original statement.

In a proof by induction, the inductive step proves which of the following?

Answer: P(k) ⇒ P(k+1)

The inductive step assumes P(k) (the inductive hypothesis) and deduces P(k+1).

Which of the following is a valid counterexample to the claim 'All prime numbers are odd'?

Answer: 2

2 is prime and even, disproving the claim that all primes are odd.

A proof that every integer n satisfies n² ≥ 0 is best classified as:

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.

When proving 'there exists an irrational number x such that x² is rational', which approach works?

Answer: Constructive existence proof giving a specific example

Taking x = √2 gives x² = 2, which is rational — a constructive existence proof.

In strong induction, the inductive hypothesis assumes:

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.