Proof Techniques
The problem
Testing shows a claim holds for the cases you tried; it cannot show a claim holds for all cases. Proof is the technology for establishing that something is true for every input — including the ones you didn't think of.
Why now
Sets and logic let us state a universal claim precisely, but stating is not establishing. No amount of enumeration settles 'this holds for all n' when there are infinitely many n; a new kind of argument — direct proof, contradiction, induction — is required.
Mental model
A proof is a chain of implications where each link is unbreakable, so the whole chain is. Induction in particular is a domino argument: prove the first domino falls and that each domino knocks over the next — this is exactly why recursion works and how you argue a loop invariant holds when the loop exits.
Requires
- Sets & LogicMathematical Thinking
Proof manipulates propositions — implication, negation, quantifiers. Contradiction and contrapositive are literally rewrite rules over logical statements; without them the moves are meaningless.
Helps
- Functions & RelationsMathematical Thinking
Many instructive first proofs are about functions (injectivity, composition), so having the vocabulary makes practice material richer — but the techniques themselves don't depend on it.
Unlocks
- Computability & the Halting ProblemComputer Science Fundamentals
- Greedy AlgorithmsComputer Science Fundamentals
- Graph Theory BasicsMathematical Thinking
- Asymptotic GrowthMathematical Thinking
- Recurrence RelationsMathematical Thinking
- Algebraic StructuresMathematical Thinking
- RecursionProgramming Fundamentals
Parallel
Used in
- Loop invariants and correctness arguments for algorithms
- Reasoning that a recursive function terminates
- Type systems (a type checker is a mechanical proof searcher)
- TLA+ / formal verification of distributed protocols
Projects
- Prove by induction that a recursive sum over a list equals the iterative sum, then map each proof step to a line of code
- Take a binary-search implementation and write down its loop invariant; use it to argue correctness at exit
Examples
- Proving √2 is irrational by contradiction — assume the opposite, derive an impossibility
- Induction on tree height to argue a balanced tree has O(log n) depth
Resources
Mastery checklist
- I can choose between direct proof, contrapositive, and contradiction for a given claim and justify the choice
- I can write a clean induction proof and identify the base case, hypothesis, and step
- I can state the loop invariant of a nontrivial loop in my own code
- I can explain why passing tests are evidence but not proof, and when the difference matters