Log in
MODULE 08

Proof Techniques: Induction, Contradiction & Contrapositive

Reference examples for each technique, plus a structural checker for your own proof outline.

Direct Proof

Claim: If n is an even integer, then n² is even.

  1. Assume n is even. By definition, n = 2k for some integer k.
  2. Then n² = (2k)² = 4k² = 2(2k²).
  3. Since 2k² is an integer, n² = 2m where m = 2k² is an integer.
  4. Therefore n² is even. ■
Proof by Contrapositive

Claim: If n² is even, then n is even.

  1. The contrapositive is: If n is odd, then n² is odd.
  2. Assume n is odd, so n = 2k+1 for some integer k.
  3. Then n² = 4k² + 4k + 1 = 2(2k²+2k) + 1, which is odd.
  4. Since the contrapositive holds, the original statement holds. ■
Proof by Contradiction

Claim: √2 is irrational.

  1. Assume, for contradiction, that √2 is rational: √2 = a/b in lowest terms.
  2. Then 2 = a²/b², so a² = 2b², meaning a² is even, so a is even: a = 2c.
  3. Substituting: 4c² = 2b² ⇒ b² = 2c², so b is also even.
  4. But then a and b share a factor of 2, contradicting 'lowest terms'. ■
Mathematical Induction

Claim: 1 + 2 + ... + n = n(n+1)/2 for all n ≥ 1.

  1. Base case: n=1. LHS = 1, RHS = 1(2)/2 = 1. True.
  2. Inductive hypothesis: assume 1+2+...+k = k(k+1)/2 holds for some k ≥ 1.
  3. Inductive step: 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2.
  4. This matches the formula for n=k+1, so by induction the formula holds for all n ≥ 1. ■
Proof by Cases

Claim: For any integer n, n(n+1) is even.

  1. Case 1: n is even. Then n = 2k for some integer k, so n(n+1) = 2k(n+1) = 2·[k(n+1)], which is even.
  2. Case 2: n is odd. Then n+1 is even, so n+1 = 2k for some integer k, so n(n+1) = n·2k = 2·(nk), which is even.
  3. Every integer is either even or odd, and both cases give an even result.
  4. Therefore n(n+1) is even for every integer n. ■
Strong Induction

Claim: Every integer n ≥ 2 can be written as a product of one or more primes.

  1. Base case: n=2. 2 is itself prime, so it trivially is 'a product of one prime'.
  2. Strong inductive hypothesis: assume every integer k with 2 ≤ k < n can be written as a product of primes.
  3. Inductive step: consider n. If n is prime, we're done. Otherwise n = a·b with 2 ≤ a,b < n. By the strong hypothesis, both a and b can be written as products of primes, so n = a·b can too.
  4. By strong induction, every integer n ≥ 2 is a product of primes. ■
Structural Induction

Claim: For every full binary tree T (every node has 0 or 2 children), the number of leaves L(T) = the number of internal nodes I(T) + 1.

  1. Base case: T is a single leaf node. Then L(T)=1, I(T)=0, and indeed 1 = 0+1.
  2. Inductive hypothesis: assume the claim L=I+1 holds for the (structurally smaller) left subtree T1 and right subtree T2.
  3. Inductive step: if T has a root with subtrees T1 and T2, then L(T) = L(T1)+L(T2), and I(T) = 1 + I(T1) + I(T2). By the hypothesis, L(T1)=I(T1)+1 and L(T2)=I(T2)+1, so L(T) = I(T1)+I(T2)+2 = (I(T)-1)+2 = I(T)+1.
  4. By structural induction, the claim holds for every full binary tree. ■
Disproof by Counterexample

Claim: Claim to disprove: For all integers n, n² + n + 1 is prime.

  1. To disprove a 'for all' statement, it suffices to find a single value of n where it fails.
  2. Try n = 4: n²+n+1 = 16+4+1 = 21.
  3. 21 = 3 × 7, which is not prime.
  4. Since the statement fails for n=4, it is false in general — this single counterexample disproves it. ■

Check Your Own Proof

What is Proof Techniques?

A mathematical proof is a logically airtight argument that a statement is always true. The standard techniques — direct proof, contrapositive, contradiction, and induction — each have specific situations where they work best.

How Does This Calculator Work?

This module is a reference and practice tool: browse the four core proof techniques with fully worked examples, or paste your own proof attempt to check its structure against the pattern for each technique.

Common Formulas & Rules

  • Direct proof: assume the hypothesis, apply definitions and known results, arrive at the conclusion.
  • Proof by contrapositive: to prove P → Q, instead prove ¬Q → ¬P (logically equivalent, sometimes far easier).
  • Proof by contradiction: assume the statement is false, derive a logical impossibility, conclude the original statement must be true.
  • Mathematical induction: prove a base case, then prove that if the statement holds for n, it holds for n+1 — this establishes it for all n.
  • Counterexample: a single case where a claimed universal statement fails, sufficient to disprove ∀x, P(x).

Worked Example

To prove "if n² is even, then n is even" by contrapositive: assume n is odd, so n = 2k+1 for some integer k. Then n² = 4k² + 4k + 1 = 2(2k²+2k) + 1, which is odd. We've shown ¬(n even) → ¬(n² even), which is logically equivalent to the original statement — and often much easier to work with directly.

Study guide: Proofs

Written for students learning this topic for the first time. Last updated October 2026.

Overview

A proof is a logical argument that a statement is true in every case. Checking examples can never prove a universal claim, but a single counterexample can disprove one. Learning to prove is largely learning to choose a technique and then justify each step.

Key ideas explained

Direct proof

Assume the hypothesis and deduce the conclusion from definitions and known facts. A typical opening is “Let n be even, so n = 2k for some integer k.”

Contrapositive

To prove P → Q, prove the equivalent statement ¬Q → ¬P. It works well when the negated conclusion gives you something concrete to compute with.

Contradiction

Assume the statement is false and derive something impossible. Classic examples are the irrationality of √2 and the infinitude of primes.

Induction

Prove a base case, assume the claim for k (the inductive hypothesis), and prove it for k + 1. Strong induction assumes all earlier cases. Induction works because every natural number is reached by repeatedly adding one, like toppling dominoes.

Worked examples

Induction: the sum of the first n integers

Problem. Prove 1 + 2 + … + n = n(n + 1)/2 for all n ≥ 1.

  1. Base case n = 1: the left side is 1 and the right side is 1·2/2 = 1.
  2. Hypothesis: assume 1 + … + k = k(k + 1)/2.
  3. Step: 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2.

Answer. The formula holds for n = k + 1 whenever it holds for k, so it holds for all n ≥ 1.

Contrapositive: squares and parity

Problem. Prove that if n² is even then n is even.

  1. The contrapositive is: if n is odd then n² is odd.
  2. Let n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd.

Answer. The contrapositive is proved, so the original statement is true.

Enter these same values in the calculator above and compare each step with the working shown here.

Common mistakes to avoid

  • Proof by example. n² + n + 41 is prime for n = 0,…,39, yet for n = 40 it equals 41².
  • Circular reasoning, such as assuming the statement for n + 1 inside an induction step.
  • Forgetting the base case, or checking one that does not match the claim.
  • Never using the inductive hypothesis, which usually means the argument is not really induction.
  • Confusing the converse with the contrapositive.

Where this shows up in computer science

  • Loop invariants and the correctness of recursive functions are inductive arguments.
  • Proofs of runtime and optimality, such as greedy exchange arguments, support algorithm design.
  • Security reductions prove that breaking a system would solve a problem believed to be hard.

Test yourself

Try each question before opening the answer.

Prove or disprove: for every integer n, n² + n is even.

True. n² + n = n(n + 1) is a product of consecutive integers, and one of them is even.

What are the three parts of an induction proof?

The base case, the inductive hypothesis, and the inductive step.

Give a counterexample to “every prime is odd”.

n = 2.

Frequently asked questions

When should I use proof by contrapositive instead of direct proof?

Use contrapositive when the direct implication is awkward to work with but its logical opposite (¬Q → ¬P) simplifies nicely — common when the hypothesis involves a property that's hard to use directly, like evenness derived from a squared term.

What's the difference between proof by contradiction and contrapositive?

Contrapositive proves P → Q by proving ¬Q → ¬P directly. Contradiction assumes the entire statement (including P) is false and derives an impossibility, which is a more general technique that works even for statements without a clean if-then structure.

Why does mathematical induction work?

Induction proves a base case holds, then proves that truth at step n guarantees truth at step n+1. Since the base case is true, step 2 follows, which makes step 3 true, and so on for every natural number — like an infinite row of dominoes.