What is a proof?
A step-by-step argument that starts from accepted facts and ends at the statement you want to establish — with every step visible.
The shape
A proof is a finite sequence of statements, each one of which is either an assumption (a hypothesis or a definition) or a logical consequence of earlier statements. The last statement is the conclusion. If every step holds, the proof is valid; if any step is unjustified, the proof fails.
The point isn't ceremony — it's that a proof compresses an unbounded number of cases into a single checkable argument.
Direct proof
To prove "if P then Q" directly, you assume P and derive Q with a chain of justified steps. Example: If n is even, then n² is even. Assume n = 2k. Then n² = 4k² = 2(2k²), which is even. QED.
Most proofs you'll meet are direct — until they aren't.
Proof by induction
For statements indexed by the natural numbers (1, 2, 3, ...), induction is the workhorse. Two steps:
1. Base case: the statement holds for n = 1. 2. Inductive step: if it holds for n, it holds for n + 1.Those two together prove it for every natural number. The base case starts the chain; the inductive step is the rule that keeps it going forever.
Flashcard · Unit 1
If P is true, then Q must be true.
Check your understanding
Which of the following is a valid proof technique for "if P then Q"?