Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 68 · Proof Techniques

How Proofs Work

Learn what a proof is, how definitions and theorems fit together, and how to write direct proofs, find counterexamples and split into cases.

Programmers test. Mathematicians prove. A test checks a handful of inputs; a proof is an argument that a statement holds for every possible input, forever, with no exceptions. When the claim is "this sorting routine works for all lists" or "this hash scheme never loses data", a proof is the only thing that can really settle it.

Proofs have a reputation for being mysterious, but they are written in a small number of recurring patterns. In this lesson you will learn the vocabulary, the most common pattern (the direct proof), how to kill a false claim with a counterexample, and how to split a problem into cases. You will also pick up the habit that makes proofs much easier: experiment in Python first, then prove.

The vocabulary

A definition fixes the meaning of a word. An integer n is even if n = 2k for some integer k; it is odd if n = 2k + 1 for some integer k. Definitions are the raw material of every proof: when a proof says "n is even", it immediately unpacks that into n = 2k.

A statement is a sentence that is either true or false, usually written with quantifiers (see Predicates and Quantifiers). A theorem is a statement that has been proved. A lemma is a helper theorem used on the way to a bigger one, and a corollary is a result that follows quickly from a theorem. A conjecture is a statement someone believes but has not proved. An axiom is a starting assumption accepted without proof.

The proof vocabulary

Definition Fixes what a word means.
Theorem A proved statement.
Lemma A helper result on the way.
Conjecture Believed, not yet proved.

Most statements you prove have the shape "if P, then Q" (see Implication and Biconditional).

1 / 2

Most theorems have the shape "for all x, if P(x) then Q(x)". To prove it, you take an arbitrary x that satisfies the hypothesis P, and you reason until you reach the conclusion Q. The word arbitrary matters: you must not pick a special value, or you have proved only one case.

Experiment first

Before you try to prove something, test it. A few seconds of code can show you that a claim is false, or hint at why it is true. Take the claim: "the sum of any two odd integers is even." Check it on many pairs, then look at what the examples have in common.

Python Test a conjecture before proving it

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.

Passing 100 tests proves nothing, but it tells you where to aim. The empty lists above suggest the first two claims are true; the last line already shows a failing case for the third claim.

Direct proof

A direct proof of "if P then Q" assumes P and walks forward, one justified step at a time, until Q appears.

Theorem. If a and b are odd integers, then a + b is even.

Proof. Let a and b be odd integers. By the definition of odd, there are integers j and k with a = 2j + 1 and b = 2k + 1. Then a + b = 2j + 2k + 2 = 2(j + k + 1). Since j + k + 1 is an integer, a + b is twice an integer, so a + b is even. ∎

The little square ∎ (or the letters QED) marks the end. Notice the pattern: unpack the definitions of the hypothesis, do algebra, repack into the definition of the conclusion. That recipe solves a very large share of introductory proofs.

The converse ("if n² is odd then n is odd") needs a different technique, which comes in the next lesson. The statement below works directly.

Theorem. If n is odd, then n² is odd.

Proof. Write n = 2k + 1. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which has the form 2m + 1 with m = 2k² + 2k an integer. So n² is odd. ∎

Python What a direct proof does, spelled out

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 code verifies the algebraic identities on a sample. The proof is the algebra itself, which holds for every integer, because it only uses ring arithmetic and nothing about specific numbers.

Counterexamples

To disprove "for all x, P(x)", you only need one x where P fails. That x is a counterexample. Disproving a universal claim is usually far easier than proving one, which is why testing is so valuable.

Claim: "for every positive integer n, n² + n + 41 is prime." It works for n = 1, 2, 3, and a great many more. It is a famous example of a pattern that holds for a long time and then fails. Let code find the first failure.

Python Hunting for a counterexample

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 first failure is n = 40, where 40² + 40 + 41 = 1681 = 41². A single such value kills the claim. But the reverse does not hold: None for the second claim means only "no counterexample below 10,000", which is not a proof.

Examples never prove a "for all" statement, and a single counterexample always disproves it. If you cannot find a counterexample, that is a hint to try proving the claim, not a proof that it is true.

Proof by cases

Sometimes a statement is easier to handle by splitting the possibilities into cases that together cover everything. The cases must be exhaustive (nothing is left out), and each is proved on its own.

Theorem. For every integer n, the number 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), which is even. Case 2: n = 2k + 1. Then n² + n = (4k² + 4k + 1) + (2k + 1) = 4k² + 6k + 2 = 2(2k² + 3k + 1), which is even. Both cases give an even number. ∎

A classic use of cases is the absolute value: |x| is defined as x when x ≥ 0 and -x otherwise, so facts about |x| are often proved by treating each sign separately. You can check case coverage mechanically on a finite range, though the real proof still has to cover all integers.

Python Cases, checked mechanically

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.

Writing a clear proof

A proof is communication. These habits make yours readable and correct:

  • State what you are proving, with the theorem written out in full before the proof.
  • Say what you assume ("Let n be an odd integer") and what you want to reach.
  • Use definitions explicitly. Write out n = 2k + 1 instead of waving at "odd".
  • Give every step a reason, even a small one: "by the definition", "since the sum of integers is an integer".
  • Introduce each name once. Do not reuse k for two different integers in the same argument (a very common source of false proofs).
  • End clearly, with the conclusion that matches the theorem, then ∎.

A direct proof, in order

Assume Let x be arbitrary with P true.
Unpack Rewrite P using its definition.
Work Algebra or logic, each step justified.
Repack Show the form of Q and finish.
1 / 2

The next lesson adds two indirect techniques for the many statements that resist this forward approach: Contradiction and Contrapositive.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is the quickest way to disprove the claim 'every prime number is odd'?

    A single counterexample refutes a universal statement. 2 is prime and even.
  2. 2. In a direct proof of 'if n is odd then n squared is odd', what is the right first step?

    A direct proof assumes the hypothesis and unpacks it with the definition: odd means n = 2k + 1 for some integer k. Testing specific values does not prove the general case.
  3. 3. A proof by cases is valid only if the cases are...

    Each case is proved separately, and the cases together must cover everything. A missing case leaves a gap in the proof.
  4. 4. Your code finds no counterexample to a claim among the first 10 million integers. What can you conclude?

    Finite testing never proves a universal statement. It only raises confidence and may suggest a proof strategy.

Summary

  • A proof shows a statement holds for every case; testing only checks some.
  • Definitions are the raw material: unpack them (odd means 2k + 1), do the algebra, repack into the conclusion.
  • A direct proof assumes the hypothesis P and derives the conclusion Q.
  • One counterexample disproves a "for all" claim; no number of examples proves one.
  • Proof by cases splits into exhaustive cases and proves each.
  • Experiment in Python first, then write a proof with stated assumptions, justified steps and a clear ending.

Next: Contradiction and Contrapositive.