Chapter 4 teaches specific proof techniques by name. Before any of that, this section settles a more basic question: what does it even mean for an argument to count as a proof at all, as opposed to something that merely sounds convincing? Getting this distinction clear now is what makes every proof from here on read as a chain you can verify, not a performance to take on faith.
Checking examples is like testing a bridge by driving one car across it a dozen times. Every trip succeeding is real evidence. It is not the same as an engineer's calculation showing the bridge holds any legal load, including the one truck nobody drove across yet. A proof is that calculation. It is an argument built to cover every case at once, not a growing pile of successful test drives that could meet its exception on the very next one.
A proof is a finite sequence of statements, each one either an assumption, a previously established fact, or a valid logical consequence of earlier statements in the sequence — ending at the claim being proved. "Valid" means the step follows by a stated, checkable rule (a definition, an algebraic identity, an earlier theorem), not merely that the step feels plausible. Checking a claim on several specific examples is not a proof of a universal claim, no matter how many examples are checked: it establishes the claim for those examples only, and a universal claim asserts something about every case, including the ones never tried.
Put a short proof back in order
These four lines prove that the sum of two even integers is even, but they've been shuffled. Click two lines to swap them until the argument reads as a single chain, each line following from the one before it.
Loading interactive…
Proof, or just evidence
Sort each argument by whether it's a genuine proof of a universal claim or only evidence (checking examples, or a plausible-sounding but unjustified leap).
Loading interactive…
Worked example
Evidence versus proof for the same claim
-
1
Claim: "n^2 - n + 1 is odd for every positive integer n." Compare checking examples against proving it.
-
2
Checking: n=1 gives 1 (odd), n=2 gives 3 (odd), n=3 gives 7 (odd). Three successes — this is evidence, not yet a proof of every n.
-
3
To prove it, reason about an arbitrary n directly: n^2-n = n(n-1) is a product of two consecutive integers, so one of them is even, making n(n-1) even for every n, not just the three checked.
-
4\boxed{n^2-n+1 = (\text{even}) + 1 = \text{odd, for every integer } n}
The proof covers every n at once because it never substituted a specific number — it reasoned about the shape every n shares (one of two consecutive integers is always even).
Loading interactive…
Who uses this
Mathematics and computer science
This distinction has a famous real cost: the claim "n^2+n+41 is prime for every non-negative integer n" holds for every single n from 0 up through 39 — forty straight successes — and then fails at n=40, where it factors evenly. Anyone who stopped checking at n=39 would have "proved" a false claim by evidence alone. Software testing runs into the identical problem: passing a large test suite is strong evidence a program is correct, but it's not a proof the program is correct for every possible input, which is exactly why formal verification (proving code correct, not just testing it) is its own field.
Check your understanding (counts toward your progress)
Which best distinguishes a genuine proof from a plausible-sounding argument?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Fixing an arbitrary, unspecified object (rather than a particular number) is what makes an argument apply to every case simultaneously.
What must every step of a valid proof have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A valid step follows from a definite, checkable rule -- not merely from feeling plausible.
Software testing that passes every test in a large suite provides...
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A passing test suite is evidence, exactly the same limited kind examples provide for a mathematical claim -- not a proof covering every possible input.
Checking a claim on five specific examples and finding it true each time is...
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Examples are genuine evidence but never cover every case a universal claim asserts -- a proof must be built for the general case.