Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 37 · Proof Techniques

Direct Proof and Proof by Cases

Learn how to write direct proofs and proofs by cases and exhaustion, with worked number-theory examples, proof-writing habits and Python experiments that guide the proof.

A proof is a finite, logically airtight argument that a statement is true, written so that a skeptical reader can check every step. This chapter surveys the main techniques. We begin with the most natural: direct proof, plus its two close relatives proof by cases and proof by exhaustion.

Anatomy of a theorem

A mathematical result has three parts: hypotheses (what we assume), conclusion (what we show) and proof (why). Most theorems look like ∀x (P(x) → Q(x)), which tells you how to start: let x be arbitrary, assume P(x), derive Q(x). That is the quantifier rule UG plus the implication rule from the natural deduction lesson.

Words you will see:

  • Definition: an agreed meaning (an integer n is even if n = 2k for some integer k).
  • Lemma: a helper result; theorem: a main result; corollary: a quick consequence.
  • Conjecture: a statement believed but not proved.

Direct proof

To prove P → Q directly: assume P, then apply definitions and known facts, step by step, until Q appears.

Theorem. If n is an even integer, then n² is even.

Proof. Let n be even. By definition, n = 2k for some integer k. Then n² = (2k)² = 4k² = 2(2k²). Since 2k² is an integer, n² is even by definition. ∎

Notice the habit: unfold the definition of what you assume, compute, and fold back into the definition of what you want.

Python Experiment first, then prove

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The third line is false, so the conjecture "the product of two odd numbers is even" has counterexamples everywhere. Experiments find such errors in seconds.

Theorem. The sum of two odd integers is even.

Proof. Let a = 2j + 1 and b = 2k + 1 for integers j, k. Then a + b = 2j + 2k + 2 = 2(j + k + 1), which is even. ∎

Proof by cases

Sometimes a statement is easiest to prove by splitting the situation into exhaustive cases and handling each one. The cases must cover every possibility; they need not be disjoint.

Theorem. For every integer n, n² + n is even.

Proof. Either n is even or n is odd.

  • Case 1: n = 2k. Then n² + n = 4k² + 2k = 2(2k² + k), even.
  • Case 2: n = 2k + 1. Then n² + n = 4k² + 4k + 1 + 2k + 1 = 4k² + 6k + 2 = 2(2k² + 3k + 1), even. In both cases n² + n is even. ∎

This is the logical rule of ∨-elimination in everyday dress. Another typical use is |x|: split into x ≥ 0 and x < 0.

Two basic proof shapes

Direct proof Assume P, derive Q
Cases Cover every possibility
Unfold definitions Replace words by meaning
Fold back Match the goal's definition

Name the cases and check they are exhaustive

1 / 2

Proof by exhaustion

If the set of possibilities is finite and small, check them all. This is legitimate, as long as the enumeration is complete and shown. A famous large example is the four-color theorem, whose original proof checked about 1,900 configurations by computer.

Claim. For every integer n, n³ ≡ n (mod 6). Since arithmetic respects congruence, only n mod 6 matters, and that takes only six values, so it suffices to test those six.

Python Proof by exhaustion over residues

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reduction step (only n mod 6 matters because arithmetic respects congruence) is the human part of the proof; the six checks are the mechanical part.

Without loss of generality

When a statement is symmetric, you may treat one case and say "without loss of generality (WLOG)": for instance, to prove something about two integers a and b, assume a ≤ b, since the roles can be swapped. Use WLOG only when the symmetry is genuinely present and say why.

Writing good proofs

  1. State the claim precisely, with quantifiers.
  2. Start by naming: "Let n be an arbitrary even integer."
  3. Use definitions explicitly.
  4. Justify every step with a definition, a prior result or algebra.
  5. End with the goal, matching its form exactly, then mark the end (∎).
  6. Reread as a skeptic: could any step hide an unjustified assumption?

Common mistakes

  • Proving a statement by examples ("it works for n = 1, 2, 3").
  • Assuming what you want to prove (circular reasoning).
  • Using the same letter for two different objects (n = 2k and m = 2k).
  • Cases that miss a possibility (for example splitting into x > 0 and x < 0 and forgetting x = 0).
  • Dividing by a quantity that might be zero.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. To prove 'if P then Q' directly, you...

    A direct proof assumes the hypothesis P and reasons to the conclusion Q.
  2. 2. What must be true of the cases in a proof by cases?

    If a possibility is left out the proof has a gap; overlap is harmless.
  3. 3. Why is 'it works for n = 1..100' not a proof of a statement about all integers?

    Only a general argument (or a finite, exhaustive check) establishes a universal statement.
  4. 4. In the proof that n² + n is even, which split of cases is used?

    Parity cases cover every integer and make the algebra easy.

Summary

  • A direct proof assumes the hypothesis and derives the conclusion, unfolding and refolding definitions.
  • Proof by cases requires an exhaustive list of cases; WLOG reduces symmetric cases.
  • Proof by exhaustion checks a finite set of possibilities completely.
  • Experiments suggest what to prove but never replace the proof.
  • Write proofs that a skeptic could verify line by line.

Next: Proof by Contrapositive and Contradiction