Proof Techniques Flashcards

Which of the following is NOT a valid method of mathematical proof?

Answer: Proof by example

A single example proves existence but cannot prove a universal statement; only a counterexample can disprove one.

To prove ∑_{k=1}^{n} k = n(n+1)/2 by induction, the base case checks:

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.

If a proof assumes 'let n be an arbitrary even integer' and derives a property, the conclusion holds for:

Answer: All even integers

Proving a property for an arbitrary even integer, with no further assumptions, establishes it universally for all even integers.

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:

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.

What is the logical form of modus tollens?

Answer: ¬Q, P ⇒ Q ⊢ ¬P

Modus tollens: given P ⇒ Q and ¬Q, we conclude ¬P — the basis of many proof by contradiction arguments.

When proving 'there are infinitely many odd numbers', the most direct approach is:

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.

In a proof by induction on a statement about divisibility, the inductive step typically uses:

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.