Not sure which lesson to do first? Find your level and get a plan →

Math · Sets & Logic · Grade 9-12

Proofs

A proof is a rigorous logical argument that establishes a statement's truth beyond doubt, proceeding from axioms and prior results through valid inference rules.


Quick Answer

A proof is a rigorous logical argument that establishes a statement's truth beyond doubt, proceeding from axioms and prior results through valid inference rules. You need one whenever a claim is about every case, such as all integers or all triangles, because checking examples, even a million of them, cannot rule out the next one. A proof starts from what is given, uses definitions (an even number is 2k), and links each step to the last until the claim is forced.

Why This Matters

A proof is the only way to know a claim holds for numbers you will never test, which is what lets later results safely build on it. It also shows why a pattern works, and that explanation often suggests the next result. Without proof, a convincing pattern can fail: n2+n+41 is prime for every n from 0 to 39 and then fails at n=40.

Intuitive Explanation

Check that the sum of two odd numbers is even: 3+5=8, 7+11=18, 101+999=1100. Every example works, but there are infinitely many odd numbers, so examples can never finish the job. A proof replaces "these cases" with "any case". Write any odd number as 2a+1, where a is an integer, and another as 2b+1. Their sum is 2a+2b+2=2(a+b+1), which is 2 times an integer, so it is even. One calculation covers every pair at once.

Each step must follow from earlier ones by a rule you could name: a definition (odd means 2a+1), algebra (collecting terms), or a result already proved. A step that sounds right but has no such reason is a gap, and a proof is only as strong as its weakest step. Direction matters too. Proving "if n is even, then n2 is even" does not prove "if n2 is even, then n is even". That second claim, the converse, happens to be true, but it needs its own argument.

One counterexample defeats a universal claim, while a million examples can't establish one. Euler's formula n2+n+41 gives primes for n=0,1,…,39, forty cases in a row, yet n=40 gives 1681=412. A derivation, such as working out the quadratic formula, can serve as a proof, but only if every step holds in every case, for example never dividing by something that could be zero.

Think of it like this. A proof is like a contract with no loopholes: every clause follows from agreed definitions, so no future case can wriggle out of it. Testing examples is like asking a few people whether they found a loophole yet. Unlike contracts, a correct proof is never overturned by a later case; only a flawed step can break it.

Core idea. A proof is a rigorous chain of valid inferences from accepted axioms to a guaranteed conclusion.


When to Use

Write a proof when a problem says prove, show that or explain why, or when a claim covers infinitely many cases: "for all integers", "every triangle", "always". Start from the definitions of the words in the claim. If the claim says "there exists" a case, one example proves it; if you suspect the claim is false, look for a single counterexample instead of a proof.

Tip. Ask: Does my argument guarantee the claim for EVERY case via valid inference, not just confirm examples?

How to Recognize It

Before writing anything, decide whether the claim is about every case, about at least one case, or is something you suspect is false, because each calls for a different kind of answer.

  1. Does the claim cover infinitely many cases, such as all integers or every triangle?

    If yes, examples cannot settle it; you need a general argument about an arbitrary object, such as 'let n be any integer'. If the claim covers only a few listed cases, checking each one is itself a proof.

  2. Does the claim say only that at least one example exists?

    If yes, one correct example proves it: 'some prime is even' is proved by 2, with no general argument needed. In reverse, a single counterexample disproves a 'for all' claim.

  3. Can you write each key word of the claim as a definition in symbols, such as odd meaning 2k+1?

    If yes, those definitions are your starting material. If not, the gap is in understanding the claim, and an informal sense of why it is true, proof intuition, has to come before the written proof.

  4. Are you asked to produce a formula from known ones rather than to show a claim holds in every case?

    If yes, that is a derivation, which counts as a proof only if each step is justified. A proof's goal is a guarantee, not a new expression.

Proofs compared with Proof (intuition), Verification by examples, and Derivation

All four rows are ways of supporting a claim, so they look alike on paper. Ask what the argument delivers: a guarantee for every case, a sense of why, evidence from a few cases, or a new formula produced from old ones.

Proofs

Meaning
Use this when a claim must be guaranteed true for all cases through valid inference, not merely verified on examples.
Key test
Does my argument guarantee the claim for EVERY case via valid inference, not just confirm examples?
Example
Prove that the sum of two odd numbers is always even.

Proof (intuition)

Meaning
The informal pre-proof sense of why it's true; a formal proof is the rigorous written argument that follows.
Key test
Use when discovering why before writing the airtight version.
Example
Sensing 2 can't be a fraction

Verification by examples

Meaning
Checking a claim on specific cases, which can suggest but never establish a universal truth.
Key test
Use to build a conjecture or find a counterexample, not to prove.
Example
Trying n=1,2,3 and seeing it works

Derivation

Meaning
Showing how a result is produced step by step; a derivation can be a proof but emphasizes producing, not guaranteeing for all.
Key test
Use when the task is to obtain a formula from known ones.
Example
Deriving the quadratic formula

Formula & Notation

How to read it: Proofs use implication symbols (⇒) and quantified statements.

Worked Examples

Example 1 — Prove a universal claim

Easy

Prove that the sum of two odd numbers is always even.
Show the steps and the answer
  1. Start from the definition: an odd number can be written 2a+1 for some integer a. Let the two odd numbers be 2a+1 and 2b+1.

    Two different letters cover every pair, including two different odd numbers; one letter would only cover a number added to itself.

  2. Add them: (2a+1)+(2b+1)=2a+2b+2.

    Collecting terms is valid algebra for any integers a and b.

  3. Factor out 2: 2a+2b+2=2(a+b+1).

    An even number is 2 times an integer, and a+b+1 is an integer because a sum of integers is an integer.

  4. Conclude: the sum is 2 times an integer, so it is even.

    Every step held for arbitrary integers a and b, so the claim holds for every pair of odd numbers.

Answer: It's always even   ■

Takeaway: Write a general case using the definition, then transform it until it matches the definition of what you want to prove.

Example 2 — Checking examples isn't proof

Standard

A student adds three pairs of odd numbers, gets even each time, and writes 'proved.' Is it?
Show the steps and the answer
  1. Look at what was checked, say 1+3=4, 5+7=12 and 9+15=24: three pairs out of infinitely many.

    Three cases leave infinitely many untested, so "always" has not been shown.

  2. Compare with a claim that fails late: n2+n+41 is prime for n=0 to 39, but 402+40+41=1681=41×41.

    Forty true examples in a row and the claim is still false, so examples can only suggest.

  3. Replace the examples with the general argument (2a+1)+(2b+1)=2(a+b+1).

    Letters stand for every odd number at once, which no list of examples can do.

Answer: No — examples don't prove a universal claim

Takeaway: Examples can suggest a pattern, and one counterexample can disprove a claim, but only a general argument proves a "for all" statement.

Example 3 — Find the mistake: one letter, two jobs

Application

Claim: for positive integers, if a divides b and b divides c, then a divides c. Noah writes: "b=ak and c=bk, so c=ak⋅k=ak2, and a divides c." Find the mistake and correct it.
Show the steps and the answer
  1. Test Noah's setup with a=2, b=6, c=30: b=2⋅3 needs k=3, but c=6⋅5 needs a multiplier of 5.

    Noah's lines force both multipliers to be the same k, and these numbers show that isn't true in general.

  2. Name the gap: nothing in the hypothesis says the two multipliers are equal.

    Using one letter for two unknowns sneaks in an extra assumption, so the argument covers only cases like a=2, b=6, c=18.

  3. Use separate letters: b=ak and c=bm for integers k and m.

    Each "divides" gets its own multiplier, so every case is covered.

  4. Substitute: c=bm=(ak)m=a(km), and km is an integer. Check: 30=2⋅15 with km=3⋅5.

    Each line follows by substitution or because integers multiply to integers, so no step is assumed.

Answer: With b=ak and c=bm, c=a(km), so a divides c; Noah's version only covered cases where both multipliers are equal.

Takeaway: Give every unknown its own letter; reusing a letter is a hidden assumption that leaves a gap in the proof.

Where You'll See It

  • Chip makers proving their arithmetic

    In 1994 Intel's Pentium chip was found to give wrong answers for a few rare divisions, and the recall cost the company about $475 million. Testing had missed them because no test can try every input. Chip makers have since used formal proofs to show that arithmetic circuits are correct for all inputs.

  • Why encryption decrypts every message

    RSA encryption, used for secure websites, scrambles a number by raising it to a power and taking a remainder. A theorem from number theory guarantees that a second power undoes the first for every possible message. Banks rely on that proof, not on trying a few messages and hoping.

Common Mistakes

  1. The slip: Treating confirming examples as a proof

    Instead: a universal claim needs an argument covering every case.

  2. The slip: Leaving a gap in the inference chain

    Instead: every step must follow by a valid rule from axioms or prior results.

  3. The slip: Assuming the converse holds because the statement does

    Instead: prove each direction separately.


Mini Practice

Try these on your own. Tap Reveal when you want to check.

  1. Prove that the product of an even number and any integer is even.

    Hint: Write the even number as 2a.

  2. Prove that (n+1)2−n2=2n+1 for every integer n, then use it to find 512−502.

    Hint: Expand (n+1)2 and subtract.

  3. Prove that the interior angles of any quadrilateral add to 360∘, using the known triangle angle sum.

    Hint: Draw one diagonal. What shapes do you get?

  4. Prove that if n is odd, then n2−1 is divisible by 8.

    Hint: Write n=2k+1 and factor what you get. Is k(k+1) odd or even?

  5. Claim: "n2+n+1 is odd for every integer n." Ari checks n=0,1,2,3 and gets 1, 3, 7, 13. Has he proved it? If not, what proves it?

    Hint: Can four cases cover every integer? Factor n2+n.

  6. Bea proved "if n is divisible by 6, then n is even." She then writes, "So every even number is divisible by 6." Correct her.

    Hint: She has reversed the statement. Test a small even number.

Want the full set?

50 practice questions for this concept — free to try, every one with a complete worked solution showing the why, not just the answer.

Frequently Asked Questions

Why isn't checking a billion cases enough?

Because some patterns break later than anyone would check. In 1919 George Pólya guessed that among the numbers from 1 to nn, for any n>1n > 1, at least half have an odd number of prime factors, counting repeats. It holds for every nn up to hundreds of millions. It was shown false in 1958, and in 1980 the first failure was found: n=906,150,257n = 906{,}150{,}257. A proof covers the case nobody has checked yet.

Can a proof be wrong?

A correct proof cannot be overturned, but a written argument can contain a hidden error, and then it was never a proof. Andrew Wiles announced a proof of Fermat's Last Theorem in 1993, and reviewers found a gap in one step. He and Richard Taylor repaired it in 1994, and the corrected proof was published in 1995. Checking by other people is part of how mathematics decides what is proved.

What is an axiom, and why accept it without proof?

An axiom is a starting statement everyone agrees to take as true, such as 'through two points there is exactly one line'. Every proof needs somewhere to start, or each claim would rest on an earlier claim forever. Axioms are chosen to be simple and believable, and changing one can create a new, consistent kind of mathematics: replacing Euclid's parallel postulate produced non-Euclidean geometry.

Is a proof done by computer a real proof?

Most mathematicians now accept it, though it was controversial at first. In 1976 Kenneth Appel and Wolfgang Haken proved the four colour theorem, that any map can be coloured with four colours so neighbouring regions differ, by having a computer check nearly 2,000 configurations that no person could check by hand. Today programs called proof assistants check every logical step of a proof, which some trust more than human reading.

Learning Path

Proofs

You are here

Next →

Nothing after this yet
You need Logical Statement (claims that are true or false), Conditional Statement ("if P then Q" and why its converse is different) and Proof (Intuition) (the informal sense of why something is true) first. Proofs add rigour: each step justified by a definition, an axiom or an earlier result. Next come specific techniques for writing them: direct proof, proof by contradiction and mathematical induction.

See Also