Home / Courses / Discrete Mathematics / Unit 2

Discrete Mathematics Unit 2: Proof techniques

A proof is a logical argument that a statement is always true. Different statements call for different proof strategies.

Covers: Direct proof, contrapositive, contradiction, mathematical induction

Study guide

A proof is a logical argument that a statement is always true. A direct proof of p → q assumes p and uses definitions, known facts and algebra to reach q. Definitions do most of the work: an integer n is even if n = 2k and odd if n = 2k + 1 for some integer k, and a rational number is a/b with integers a, b and b ≠ 0.

A proof by contrapositive proves ¬q → ¬p instead, which is equivalent. It's useful when the negated conclusion gives you something concrete, like "if n² is even then n is even": assume n is odd and show n² is odd.

A proof by contradiction assumes the statement is false and derives something impossible. The classic example is that √2 is irrational: assume √2 = a/b in lowest terms, and show both a and b must be even, a contradiction.

To disprove a universal statement, find a single counterexample. Proofs by cases split into exhaustive possibilities, like n even or odd.

Mathematical induction proves statements about all integers n ≥ n₀. The base case shows P(n₀) is true. The inductive step assumes P(k) (the inductive hypothesis) and proves P(k + 1). Together they cover every integer, like dominoes falling. Strong induction assumes P is true for all values up to k, which is useful for recurrences and factorization. Common uses include sum formulas, divisibility and inequalities.

To show a state can never be reached, find an invariant: a quantity, such as the parity of a count, that every allowed move preserves. Prove by induction on the number of moves that it holds in every reachable state, then check that the target state violates it. To prove p ↔ q, prove both p → q and q → p, each by any method. For divisibility claims, a proof by cases on the remainder (n = 3k, 3k + 1 or 3k + 2) usually works.

Key ideas

• Direct proof: assume the hypothesis and derive the conclusion.
• Contrapositive: prove ¬q → ¬p instead.
• Contradiction: assume the statement is false and reach an impossibility.
• Induction: prove a base case, then show P(k) → P(k + 1).
• A single counterexample disproves a universal statement.

Formulas and rules

Common mistakes

• Proving with examples. Examples never prove a universal statement.
• In induction, assuming P(k + 1) instead of proving it.

Words to know

Two steps of mathematical induction

Base case, then inductive step P(k) → P(k + 1).

Counterexample

One case that disproves a "for all" statement.

Proof by contradiction

Assume the statement is false and derive a contradiction.

Definition of an odd integer

n = 2k + 1 for some integer k.

Proof by contrapositive

Prove ¬q → ¬p to show p → q.

Even integer

n = 2k for some integer k.

Direct proof

Assume p, reason to q.

Proof by cases

Split into exhaustive cases and prove each.

Base case

Proving P(n₀) in induction.

Inductive hypothesis

Assuming P(k) to prove P(k + 1).

Strong induction

Assume P is true for all values up to k.

Rational number (definition)

a/b with integers a, b and b ≠ 0.

Sample practice questions

5 more questions like these, from level 1 to 5, are in the practice set.