Proof Techniques

Direct proof chains forward, contradiction assumes the opposite and breaks it, and induction topples an infinite ladder from one anchored rung.

Partial sums 1, 3, 6, 10, 15 march under the formula n times n plus 1 over 2, so induction carries the truth up the whole ladder

Why Does This Exist?

"Why should I believe that?" has three standard answers, and reaching for the wrong one wastes hours: chaining forward when the opposite assumption breaks faster, attempting infinite cases one by one, or hand-waving a universal that induction would settle. Every convergence claim, complexity bound, and correctness argument in ML uses one of these three shapes.

Knowing the shapes also means recognizing them in others' work and spotting where each can silently fail: a direct chain with a weak link, a contradiction that never reaches absurdity, an induction missing its base. Claims and quantifiers are in propositional logic and quantifiers.

The one idea you need first

A proof is a finite chain of valid steps from agreed starting points (axioms, definitions, already-proven results) to the conclusion, checkable by anyone. The technique is the chain's shape: forward construction, opposite-assumption demolition, or rung-by-rung climb. Shape first, details second.

Think of It Like This

Three ways to certify a ladder is climbable

Direct proof walks the ladder: foot on rung one, hands steady, step by step to the top, narrating each safe move. Contradiction hires a skeptic who claims the top is unreachable, then shows that claim forces something absurd, like the skeptic standing on the top while denying it. Induction checks the first rung holds and the rungs are linked, then declares the whole ladder sound without climbing every rung.

Walking suits short ladders, skeptics suit claims whose denial explodes quickly, and linkage suits infinite ladders no one can fully climb. The analogy stops at certainty: real ladders still need inspection, while a correct proof needs no rechecking ever.

How It Actually Works

The three shapes, each with its contract:

Direct. Assume the premises, apply definitions and valid inferences forward, arrive at the conclusion. Best when definitions unfold naturally toward the goal. Example shape: even means $2k$ ; sum of evens $2k + 2m = 2(k+m)$ , visibly even.
Contradiction. Assume the conclusion is false alongside the premises, derive something impossible ( $0 = 1$ , a number both even and odd), and conclude the assumption was wrong. Best when the denial is explosive. Classic: $\sqrt{2}$ is irrational, since rationality forces a fraction reducible forever.
Induction. Prove a base case ( $n = 1$ ), then prove the step (if true for $k$ , true for $k+1$ ). The two together topple all positive integers like dominoes. Best for claims about all natural numbers, loop correctness, and recurrences.

Induction's contract is strict: base without step proves one case; step without base proves a chain floating in air. Both halves are mandatory, and the step must use the hypothesis for $k$ genuinely, not re-prove from scratch.

Worked example

Prove $S(n) = 1 + 2 + \cdots + n = n(n+1)/2$ by induction, then evaluate at 100:

Base ( $n = 1$ ): left side 1, formula $1 \times 2/2 = 1$ . Anchored.
Step: assume $S(k) = k(k+1)/2$ . Then $S(k+1) = S(k) + (k+1) = (k(k+1) + 2(k+1))/2 = (k+1)(k+2)/2$ . Exactly the formula at $k+1$ . Linked.
Conclusion: holds for all positive integers. At $n = 100$ : $100 \times 101/2 = 5050$ .

Pairing check: $(1+100) + (2+99) + \cdots$ gives fifty pairs of 101, $50 \times 101 = 5050$ . Independent route, same number. The ladder stands.

Watch Out For

Induction with an unproven base case

The step "if $k$ then $k+1$ " is vacuously safe when nothing is ever true: it proves a chain of nothings. Classic joke theorems ("all horses are the same color") hide the failure in a base case that is asserted, not shown, usually for $n = 1$ where the step's overlap assumption already breaks.

Verify the base by hand computation, visibly, before admiring the step. If the base needs the step's machinery, the argument is circular.

Contradiction that ends in surprise instead of absurdity

Deriving something unexpected ("...so $n$ must be negative") is not a contradiction unless negativity was ruled out. Many failed contradiction attempts end at a weird-but-possible statement and declare victory, proving nothing.

Name the impossibility in advance: which axiom or premise does the derived statement violate? If none, the assumption survives and a different technique is needed.

The Quick Version

Direct proof chains premises forward through definitions to the goal.
Contradiction assumes the denial and derives an impossibility.
Induction proves a base case plus a $k$ -to- $k+1$ step, covering all integers.
$1 + \cdots + 100 = 5050$ by induction, confirmed independently by pairing.
Base without step, or step without base, proves nothing: both are mandatory.
Failed contradictions end in weirdness, not impossibility; demand the violation.