Direct proof
Assume the hypotheses and derive the conclusion.
Find a concept
REFERENCE SHEET
Proof techniques
Choose the logical shape of an argument before choosing its algebra.
Before this Sets & maps
P ⇒ Q ⇔ ¬Q ⇒ ¬P
Definitions
Contradiction
Assume the negation of the desired claim and derive an impossibility.
Induction
Prove a base case and a step from a statement at n to the statement at n+1.
Key theorems
Induction principle
If P(0) holds and P(n) implies P(n+1) for every integer n≥0, then P(n) holds for every integer n≥0.
Well-ordering of ℕ
Every nonempty subset of the nonnegative integers has a least element; this supports minimal-counterexample arguments.
Notable applications
Algorithms
Loop invariants and induction establish that repeated operations preserve correctness.
Structure theorems
Induction on dimension or group order reduces large objects to smaller ones.
Work it out
Try before revealing01 / Prove
Prove 1+⋯+n=n(n+1)/2 for n≥1.
Hint
Add n+1 to the induction hypothesis.
Solution
The base case is 1=1. If the formula holds at n, the next sum is n(n+1)/2+(n+1)=(n+1)(n+2)/2.
02 / Find a counterexample
Is every continuous real function differentiable?
Hint
Look for a corner.
Solution
No. f(x)=|x| is continuous everywhere, but its left and right derivatives at 0 are −1 and 1.
Connect the ideas
Build on this
These sheets use this topic as a prerequisite.
Go deeper
Further reading and full-length treatments: