Proof Techniques: Induction and Contradiction For students.

A mathematical proof is a watertight argument that a statement is true — not because examples suggest it, but because logic demands it. Two of the most powerful proof techniques in computer science are mathematical induction, which proves statements about all natural numbers by a domino-like chain, and proof by contradiction, which proves a statement by showing its denial leads to absurdity.

Computer science runs on guarantees: that a loop computes the right sum, that a data structure stays balanced, that an algorithm terminates. Induction proves properties of recursive structures and loops; contradiction establishes impossibility results like the undecidability of the halting problem.

Key Concepts

• Mathematical induction: to prove P(n) for all n ≥ 1: prove the base case P(1), then the inductive step — assuming P(k), derive P(k+1).
• Strong induction: the step may assume P(1) through P(k), not just P(k).
• Proof by contradiction: assume the negation of the claim, derive an impossibility, conclude the claim holds.
• Contrapositive: prove "if P then Q" via "if not Q then not P" — logically equivalent, sometimes easier.
• Loop invariants: induction for programs — a property true before each iteration, proved by induction on the count.

How It Works

Induction template: state P(n), verify P(1) by calculation, assume P(k) for arbitrary k, manipulate to obtain P(k+1). The base starts the domino chain; the step topples each domino into the next.

Contradiction template: suppose the claim is false, follow the consequences until two clash (a number both even and odd), and conclude the supposition was impossible. Classic example: assuming √2 = p/q in lowest terms forces p and q both even — contradicting "lowest terms".

Worked Example

Prove by induction that 1 + 2 + … + n = n(n+1)/2 for all n ≥ 1:

1. Base (n = 1): left = 1; right = 1x2/2 = 1. Equal.
2. Hypothesis: assume 1 + … + k = k(k+1)/2.
3. Step: add (k+1) to both sides: left becomes 1 + … + k + (k+1); right becomes k(k+1)/2 + (k+1).
4. Simplify: (k^2 + k)/2 + (2k + 2)/2 = (k^2 + 3k + 2)/2 = (k+1)(k+2)/2 — the formula with n = k+1.

Check n = 100: 100x101/2 = 5050. One short argument covers all infinitely many n — induction's power.

Common Misconceptions

• Many examples count as proof. A million examples cannot rule out a counterexample at a billion — only a general argument covers all cases.
• The base case is a skippable formality. Without it the chain never starts — the faulty "all horses are the same color" proof collapses here.
• Contradiction proves the opposite. It refutes the negation of the claim — logically equivalent to establishing the claim.

Real-World Applications

• Algorithm correctness: loop invariants prove sorting and search correct.
• Complexity analysis: recurrences like T(n) = 2T(n/2) + n are solved and verified by induction.
• Impossibility results: contradiction proves the halting problem undecidable and √2 irrational.
• Data structures: induction proves a heap of n nodes has logarithmic height.

Induction conquers the infinite by chaining one case to the next; contradiction conquers the impossible by showing the alternative self-destructs. Together they are the two moves behind most proofs in computer science — from the sum 1 to n to the limits of computation itself.