Direct proof, proof by contradiction, proof by contrapositive, mathematical induction (weak and strong), and the well-ordering principle — with worked examples and step-by-step strategies.
Assume P, reason logically step by step, arrive at Q. Works best when the hypothesis gives you something concrete to manipulate algebraically.
Assume the conclusion is false, then derive an impossible statement. If the assumption leads to a contradiction, the original claim must be true.
Instead of proving P → Q, prove ¬Q → ¬P. These are logically equivalent. Useful when the negation of Q is easier to work with than P.
Prove a statement for a base case (e.g., n = 1), then prove that if it holds for k it must hold for k+1. Covers all positive integers.
A direct proof proves a conditional statement P → Q by assuming P is true and deriving Q through a sequence of logical steps. Each step follows from definitions, axioms, previously proven theorems, or algebra applied to earlier steps.
State what you are given
Write "Assume P" or "Let [hypothesis]." Be explicit about what you are starting from.
Unpack definitions
Translate abstract conditions into algebra. 'n is even' becomes 'n = 2k for some integer k.'
Perform algebraic manipulation
Substitute, expand, factor, simplify. Each step must follow logically from the last.
Arrive at the conclusion
Show that Q holds and state "Therefore Q" or use the QED symbol ∎.
Given: n is odd, m is odd.
Step 1: n is odd → n = 2a + 1 for some integer a
Step 2: m is odd → m = 2b + 1 for some integer b
Step 3: nm = (2a + 1)(2b + 1)
Step 4: = 4ab + 2a + 2b + 1
Step 5: = 2(2ab + a + b) + 1
Step 6: Let c = 2ab + a + b (an integer)
Therefore nm = 2c + 1, which is odd. ∎
Proof by contradiction (Latin: reductio ad absurdum) assumes that the statement to be proven is FALSE, then shows that this assumption leads to a logical impossibility. The impossibility forces the assumption to be wrong, so the original statement must be true.
Assume the negation
Write 'Assume for contradiction that [statement] is false' or equivalently 'Assume ¬Q.'
Reason from the assumption
Use the false assumption together with the given hypothesis P to derive consequences.
Find the contradiction
Arrive at a statement of the form A and ¬A, or violate a known theorem, definition, or axiom.
Conclude
State "This is a contradiction. Therefore our assumption was false, and [original statement] is true." ∎
Assume for contradiction that √2 is rational.
Then √2 = p/q where p, q are integers with no common factors (in lowest terms).
Square both sides: 2 = p²/q²
So p² = 2q² → p² is even → p is even (if p² is even, p must be even)
Write p = 2k. Then p² = 4k², so 4k² = 2q², giving q² = 2k².
So q² is even → q is even.
Contradiction: p and q are both even, but we assumed p/q is in lowest terms. ∎
Therefore √2 is irrational.
Assume for contradiction that there exists a greatest integer N.
Consider N + 1. Since N + 1 is an integer and N + 1 > N,
this contradicts N being the greatest integer. ∎
Therefore no greatest integer exists.
P → Q is logically equivalent to ¬Q → ¬P
Instead of proving "if P then Q" directly, you prove "if not Q then not P." These two statements always have the same truth value. This technique is most useful when the negation of Q provides a cleaner algebraic starting point than P does.
| Name | Form | Equivalent to Original? |
|---|---|---|
| Conditional (original) | P → Q | Yes (itself) |
| Contrapositive | ¬Q → ¬P | Yes — always |
| Converse | Q → P | Not necessarily |
| Inverse | ¬P → ¬Q | Not necessarily |
Why contrapositive? Starting from "n² is even" to recover information about n is awkward. The contrapositive — "if n is odd then n² is odd" — is a clean direct proof.
Prove contrapositive: if n is odd, then n² is odd.
Assume n is odd → n = 2k + 1 for some integer k
n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1
n² = 2(integer) + 1 → n² is odd. ∎
By contrapositive equivalence, the original statement "if n² is even then n is even" is proven.
Contrapositive: if x is even OR y is even, then xy is even.
Case 1: x is even → x = 2a → xy = 2ay → xy is even. ✓
Case 2: y is even → y = 2b → xy = 2bx → xy is even. ✓
Both cases give xy even. Contrapositive proven, so original follows. ∎
Mathematical induction proves that a statement P(n) holds for all positive integers n ≥ n₀. Think of it as an infinite chain of dominoes: you knock over the first one (base case) and prove each domino knocks over the next (inductive step).
Step 1: Base Case
Verify P(n₀) directly. Substitute the smallest value (usually n = 1) into both sides of the equation or into the statement and confirm it is true.
Step 2: Inductive Step
Assume P(k) is true (inductive hypothesis). Using only this assumption plus algebra, prove P(k+1) is true. Do NOT assume what you are trying to prove.
Base Case (n = 1):
Left side: 1
Right side: 1·(1+1)/2 = 1·2/2 = 1 ✓
Inductive Step:
Assume: 1 + 2 + ⋯ + k = k(k+1)/2 [Inductive Hypothesis]
Prove: 1 + 2 + ⋯ + k + (k+1) = (k+1)(k+2)/2
LHS = [1 + 2 + ⋯ + k] + (k+1)
= k(k+1)/2 + (k+1) [by inductive hypothesis]
= (k+1)[k/2 + 1]
= (k+1)(k + 2)/2
= RHS ✓ By induction, the formula holds for all n ≥ 1. ∎
Base Case (n = 1):
1³ − 1 = 0. Since 3 | 0, base case holds. ✓
Inductive Step:
Assume 3 | k³ − k, i.e., k³ − k = 3m for some integer m.
(k+1)³ − (k+1)
= k³ + 3k² + 3k + 1 − k − 1
= (k³ − k) + 3k² + 3k
= 3m + 3(k² + k)
= 3(m + k² + k)
3 divides (k+1)³ − (k+1). By induction, 3 | n³ − n for all n ≥ 1. ∎
Strong induction uses a more powerful inductive hypothesis: instead of assuming only P(k), you assume P(1), P(2), ..., P(k) are ALL true, then prove P(k+1). Strong and weak induction are logically equivalent — each implies the other — but strong induction is more convenient when proving P(k+1) requires cases beyond the immediately preceding one.
Assume P(k) is true.
You only get to use the single case k to prove k+1. Works when each step depends only on the one before it.
Assume P(1), P(2), ..., P(k) are all true.
You may use any earlier case to prove k+1. Essential for recurrences that jump back more than one step.
• Recurrences that reference more than one previous term (e.g., Fibonacci: F(n) = F(n−1) + F(n−2))
• Proving every integer ≥ 2 has a prime factorization (breaking n into smaller factors)
• Game theory arguments where a position reduces to sub-positions of arbitrary smaller size
• Divide-and-conquer arguments where problem size decreases by more than 1
Base Case (n = 2):
2 is prime, so 2 is its own prime factor. ✓
Strong Inductive Step:
Assume every integer j with 2 ≤ j ≤ k has a prime factor.
Consider n = k + 1:
Case 1: k+1 is prime → it is its own prime factor. ✓
Case 2: k+1 is composite → k+1 = a·b with 2 ≤ a ≤ k.
By inductive hypothesis, a has a prime factor p.
Since p | a and a | (k+1), we get p | (k+1). ✓
By strong induction, every integer ≥ 2 has a prime factor. ∎
Every non-empty set of positive integers has a least element.
The well-ordering principle is deceptively simple but extraordinarily powerful. It is logically equivalent to mathematical induction, and either can be derived from the other. In proofs it appears most naturally in contradiction arguments: assume the set of counterexamples is non-empty, take the smallest counterexample, then derive an even smaller one — contradicting minimality.
Division Algorithm
Given integers a and d > 0, there exist unique q and r with 0 ≤ r < d and a = qd + r. Well-ordering guarantees the least non-negative remainder exists.
Euclidean Algorithm
The sequence of remainders in gcd(a, b) is strictly decreasing and bounded below by 0, so it terminates — guaranteed by well-ordering.
Prime Factorization
If some integer ≥ 2 lacked a prime factorization, take the smallest such. It can't be prime, so it factors — contradicting minimality.
Induction Equivalence
Well-ordering implies induction: if P(1) holds and P(k) → P(k+1), the set of failures would have a minimum — but that minimum's predecessor would force a failure below it.
When the domain splits into a finite number of cases that collectively cover every possibility, you can prove a statement by verifying it in each case separately. The cases must be exhaustive (cover everything) and the argument must work for each.
Every integer is either even or odd. Consider both cases.
Case 1: n is even.
n = 2k → n² − n = 4k² − 2k = 2(2k² − k) → even. ✓
Case 2: n is odd.
n = 2k+1 → n² − n = (2k+1)² − (2k+1)
= 4k²+4k+1−2k−1 = 4k²+2k = 2(2k²+k) → even. ✓
Both cases verified. n² − n is even for all integers n. ∎
x and y each can be non-negative or negative: four cases.
Case 1: x ≥ 0, y ≥ 0. |xy| = xy = |x|·|y| ✓
Case 2: x ≥ 0, y < 0. |xy| = |x(−|y|)| = x|y| = |x|·|y| ✓
Case 3: x < 0, y ≥ 0. By symmetry with Case 2. ✓
Case 4: x < 0, y < 0. xy = (−|x|)(−|y|) = |x||y| > 0, so |xy| = |x|·|y| ✓
All four cases verified. ∎
| Situation | Recommended Method |
|---|---|
| Hypothesis gives you algebra to work with directly | Direct proof |
| Negation of conclusion is cleaner than the hypothesis | Contrapositive |
| Proving something is impossible or unique | Contradiction |
| Statement holds for all positive integers (formula, divisibility) | Induction |
| Recurrence references cases more than 1 step back | Strong induction |
| Small finite domain or clear parity/sign cases | Exhaustion / Cases |
| Proving a minimum or maximum exists among integers | Well-ordering |
Circular Reasoning
Never use the conclusion to prove itself. Each step must follow from prior steps, not from Q itself.
Assuming What You Prove (Induction)
In the inductive step, you assume P(k) only — you cannot assume P(k+1) before the step is complete.
Confusing Contrapositive with Converse
Proving Q → P (converse) does NOT prove P → Q. Only the contrapositive ¬Q → ¬P is equivalent.
Missing the Base Case
Induction without a base case proves nothing. Even if the inductive step is perfect, you need at least one verified starting point.
Non-Exhaustive Cases
When proving by cases, ensure the cases cover ALL possibilities. Check that no scenario falls between your cases.
Using Examples as Proof
Verifying a statement for n = 1, 2, 3 does not prove it for all n. A proof must cover the general case.
A direct proof starts from the hypothesis (what you are given) and uses definitions, axioms, and previously proven theorems in a logical chain of steps that leads directly to the conclusion. The structure is: assume P is true, then reason step by step until you arrive at Q. For example, to prove 'if n is even then n² is even': assume n is even, so n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² = 2·(integer), so n² is even. Direct proof works best when the hypothesis gives you something concrete to work with algebraically.
Proof by contradiction (reductio ad absurdum) assumes the negation of what you want to prove, then derives a logical contradiction — a statement that is both true and false simultaneously. If the assumption leads to a contradiction, the assumption must be false, so the original statement must be true. Structure: (1) Assume the conclusion is false. (2) Reason logically from this assumption. (3) Arrive at a contradiction (e.g., 0 = 1, or n is both even and odd). (4) Conclude the original statement is true. Classic example: proving √2 is irrational — assume √2 = p/q in lowest terms, square both sides, show both p and q must be even (contradicting 'lowest terms').
For a conditional statement P → Q (if P then Q), the contrapositive is ¬Q → ¬P (if not Q then not P), and the converse is Q → P (if Q then P). The contrapositive is logically equivalent to the original statement — proving the contrapositive proves the original. The converse is NOT logically equivalent; it may be true or false independently. Example: original — 'if a number is divisible by 4, then it is even'. Contrapositive — 'if a number is not even, then it is not divisible by 4' (true, equivalent to original). Converse — 'if a number is even, then it is divisible by 4' (false — 6 is even but not divisible by 4).
Use proof by contrapositive when the negation of the conclusion is easier to work with than the hypothesis. A strong signal is when the hypothesis involves an existential statement ('there exists') or a disjunction ('or'), but the contrapositive's negation gives you a universal statement or a conjunction that you can manipulate directly. Also consider contrapositive when direct proof requires you to 'pull a trick out of nowhere' — the contrapositive form often yields a cleaner algebraic path. Example: proving 'if n² is odd then n is odd' — direct proof is awkward because you start with n² odd and must recover n. Contrapositive — 'if n is even then n² is even' — is a clean two-line direct proof.
Mathematical induction has two mandatory steps: (1) Base Case — prove the statement P(n) is true for the smallest value in the domain, usually n = 1 (or n = 0). Substitute this value and verify the statement holds directly. (2) Inductive Step — assume P(k) is true for an arbitrary positive integer k (this is the inductive hypothesis). Using only this assumption plus algebra, prove P(k+1) is true. If both steps succeed, by the principle of mathematical induction, P(n) is true for all positive integers n. Think of it like dominoes: the base case knocks over the first domino, and the inductive step guarantees each domino knocks over the next.
Strong induction (also called complete induction) differs from weak (standard) induction in the inductive hypothesis: instead of assuming only P(k), you assume P(1), P(2), ..., P(k) are ALL true, then prove P(k+1). Strong induction is logically equivalent to weak induction but is more powerful when proving P(k+1) requires not just the immediately preceding case but earlier ones too. Use strong induction when: the recurrence relation jumps back more than one step (e.g., Fibonacci sequences), when proving divisibility or prime factorization results, or when breaking a problem into sub-problems whose sizes are not simply k and k+1.
The well-ordering principle states that every non-empty set of positive integers has a least element. This principle is logically equivalent to mathematical induction — each can be used to prove the other. In proofs, well-ordering appears when you assume for contradiction that the set of counterexamples to a statement is non-empty, then derive a contradiction by finding a counterexample smaller than the 'smallest' one. Well-ordering is used to prove the division algorithm, Euclidean algorithm termination, and properties of prime numbers. It underpins the guarantee that induction 'reaches' every natural number.
To prove a sum formula like 1 + 2 + 3 + ⋯ + n = n(n+1)/2 by induction: Base case (n = 1): Left side = 1. Right side = 1·2/2 = 1. ✓. Inductive step: Assume 1 + 2 + ⋯ + k = k(k+1)/2. Prove the formula holds for k+1: 1 + 2 + ⋯ + k + (k+1) = k(k+1)/2 + (k+1) [using inductive hypothesis] = (k+1)[k/2 + 1] = (k+1)(k+2)/2. This matches the formula with n = k+1. By induction, the formula holds for all positive integers n. The key technique is always adding the next term to both sides and factoring algebraically.
Proof by exhaustion (or proof by cases) proves a statement by splitting the universe of discourse into a finite, exhaustive, mutually exclusive set of cases and verifying the statement holds in each case. It is valid whenever the number of cases is finite and you genuinely cover all possibilities. Example: proving 'for any integer n, n² − n is even' — Case 1: n is even, so n = 2k; then n² − n = 4k² − 2k = 2(2k² − k), which is even. Case 2: n is odd, so n = 2k+1; then n² − n = (2k+1)² − (2k+1) = 4k² + 4k + 1 − 2k − 1 = 2(2k² + k), which is even. Both cases confirmed — proof complete.
Interactive proof problems with step-by-step feedback and private tutoring — free to try.
Start Practicing Free