Foundations
Basic Proof Techniques
Difficulty: Advanced
Goldbach's conjecture has been verified for every even integer up to 4 10^18, yet mathematicians still call it a conjecture because no amount of testing covers every case. Algorithm correctness has the same shape: a function can pass a...
Basic Proof Techniques
Goldbach's conjecture has been verified for every even integer up to 4 * 10^18, yet mathematicians still call it a conjecture because no amount of testing covers every case. Algorithm correctness has the same shape: a function can pass a hundred unit tests and still fail on the empty list or the input size your tests never reached.
Basic Proof Techniques equips you with the small set of argument styles that turn intuition into certainty about correctness, complexity bounds, and data structure invariants. Direct proof chains definitions and prior facts to a claim. Proof by contradiction assumes the opposite and derives a logical impossibility, as in the irrationality of sqrt(2) and the Omega(n log n) lower bound for comparison sorts. Mathematical induction, in weak and strong forms, proves statements over the natural numbers via a base case and an inductive step, the backbone of recurrence solutions and loop invariants. Proof by contraposition swaps P implies Q for the equivalent not Q implies not P, and proof by cases breaks a claim into exhaustive subcases.
This lesson builds on Discrete Mathematics Basics, where you met sets, propositional logic, implications, and the first taste of formal proof. Here those informal sketches become the disciplined patterns that algorithm analysis, theoretical CS, and clean engineering arguments all rely on.
With proofs in hand, you have completed the foundations track and are ready to step into Arrays & Strings and the rest of the data structures curriculum, armed to analyze every operation rigorously.
Prerequisites:
Discrete Mathematics BasicsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Construct a direct proof to establish a mathematical claim about algorithms or data structures.
Apply proof by contradiction to show that a statement must be true by deriving a logical impossibility.
Prove statements about natural numbers using weak mathematical induction (base case + inductive step).
Use strong induction when the inductive hypothesis requires all preceding cases, not just the immediate predecessor.
Employ proof by contraposition and proof by cases to handle conditional and multi-branch claims.
Apply proof techniques to verify algorithm correctness and establish complexity bounds.
Why This Matters
01
Algorithm correctness proofs rely on induction and loop invariants -- without these tools you are guessing that your code works rather than knowing it.
02
Understanding proof by contradiction is essential for grasping why certain problems are NP-hard or why particular lower bounds hold (e.g., comparison-based sorting requires Omega(n log n)).
03
Proof by induction is the backbone of recurrence relation analysis: every application of the Master Theorem or substitution method involves an inductive argument.
04
Technical interviews at top companies sometimes ask you to argue why your algorithm is correct -- being able to articulate an invariant-based argument sets you apart.
Key Terms
8 terms you'll encounter in this lesson
Direct Proof
A proof that proceeds from known facts (axioms, definitions, previously proven theorems) through a chain of logical deductions to arrive directly at the conclusion.
Proof by Contradiction
A proof technique where you assume the negation of the statement you want to prove, then derive a logical contradiction, thereby concluding the original statement must be true. Also called reductio ad absurdum.
Mathematical Induction
A proof technique for statements about natural numbers. You prove a base case (usually n = 0 or n = 1), then prove that if the statement holds for n = k, it also holds for n = k + 1. This establishes the statement for all natural numbers.
Strong Induction
A variant of induction where the inductive hypothesis assumes the statement holds for all values from the base case up to k (not just k), and you prove it holds for k + 1. Logically equivalent to weak induction but sometimes easier to apply.
Contraposition
The logical equivalence that 'if P then Q' is the same as 'if not Q then not P'. Proof by contraposition proves the latter to establish the former.
Loop Invariant
A property that is true before the loop begins, maintained by each iteration, and (combined with the loop termination condition) implies the desired postcondition. Proving a loop invariant is an application of mathematical induction.
Base Case
The initial step in a proof by induction where you verify the statement directly for the smallest value (e.g., n = 0 or n = 1). Without a valid base case, the entire induction collapses.
Inductive Step
The step in a proof by induction where you assume the statement holds for some value k (the inductive hypothesis) and then prove it holds for k + 1.
Heads Up
Common misconceptions to watch out for
"In induction, the inductive step alone is enough -- the base case is just a formality"
The base case is essential. Without it, you could 'prove' false statements. For example, you could inductively 'prove' that all horses are the same color -- the argument fails because the base case (n = 1 to n = 2 transition) does not hold. Always verify the base case independently.
"Proof by contradiction and proof by contraposition are the same thing"
They are related but different. Contraposition proves 'if P then Q' by proving 'if not Q then not P' -- it is a direct logical equivalence. Contradiction assumes the entire statement is false and derives an impossibility. Contraposition is cleaner when the statement has an if-then structure.
"Induction only works for summation formulas"
Induction works for any property indexed by natural numbers: divisibility claims, inequalities, tree properties, algorithm correctness (via loop invariants), and recursive algorithm analysis. It is far more general than just summing series.
"Testing many examples is the same as a proof"
No matter how many examples you check, you have not proved the statement for all cases. Goldbach's conjecture has been verified for numbers up to 4 x 10^18 but remains unproven. A proof must cover every case, which is exactly what techniques like induction achieve.