1
Write a correct induction proof
Base case, explicit inductive hypothesis, and a step that actually uses it — the three parts a proof is graded on, and the three it usually loses.
Course · Discrete Mathematics
Induction and Recursion
Logic and Proof ended by showing that checking cases is not proving. This is the answer: prove P(k) → P(k+1) once and the claim holds for every n you could ever check and every one you could not. Then the same idea applied to definitions, to data, to algorithms and to recurrences.
P(base) and ∀k ≥ base. P(k) → P(k+1) ⟹ ∀n ≥ base. P(n)
strong: P(base ..k) → P(k+1)
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ ⟹ characteristic equation r² = c₁r + c₂
T(n) = aT(n/b) + nᵈ ⟹ compare log_b a with d
What this course is about
- Subject
- Discrete Mathematics
- Lessons
- 12
- Format
- Interactive
Overview
What you will be able to do
By the end you can prove a statement about every natural number, solve the recurrences Algorithms and Complexity will produce, and prove an algorithm does what it claims.
2
Choose ordinary or strong induction
Recognise the claims where P(k) alone is not enough, and state the stronger hypothesis correctly rather than reaching for it by habit.
3
Define and reason about recursive objects
Recursive definitions of sequences, sets and structures, and the structural induction that proves things about them.
4
Solve a recurrence
Linear homogeneous by characteristic roots, nonhomogeneous by a particular solution, and divide-and-conquer by the master theorem.
5
Prove an algorithm correct
Termination by a quantity that strictly decreases and is bounded below, and correctness by strong induction on the input for a recursion or by an invariant for a loop — the two obligations of “Recursive Algorithms and Correctness” and “Loop Invariants and Program Correctness”, neither of which is worth anything alone.
Lessons
12 lessons
Induction comes first, then recursion, then recurrences, and “Loop Invariants and Program Correctness” applies all three to program correctness.
The Well-Ordering PrincipleEvery nonempty set of naturals has a least element — and why that is enough.Not marked
Mathematical InductionBase case, inductive step, conclusion — and the step must use the hypothesis.Not marked
Induction with Sums and ProductsThe standard family of identities, and the pattern they share.Not marked
Induction with Inequalities and DivisibilityTwo families where the base case is often not n = 1.Not marked
Strong InductionAssume every earlier case, not only the previous one.Not marked
Recursive DefinitionsDefining an object in terms of smaller instances of itself.Not marked
Structural InductionInduction over how an object was built, not over a number.Not marked
Recursive Algorithms and CorrectnessAn algorithm that calls itself, and the induction that proves it right.Not marked
Recurrence RelationsSequences defined by their own earlier terms.Not marked
Solving Linear RecurrencesCharacteristic roots, repeated roots, and particular solutions.Not marked
Divide-and-Conquer RecurrencesT(n) = aT(n/b) + f(n), and the one comparison that solves it.Not marked
Loop Invariants and Program CorrectnessInduction, applied to a loop instead of to a number.Not marked
Recommended background
Proof technique and set notation.
Practice suggestions
Write every proof out in full, including the sentence that says where the inductive hypothesis was used. A step that never invokes P(k) is not an induction proof, however true its conclusion.
Spend real time in the lab of “The Well-Ordering Principle”. Two of its statements are false and survive dozens of checks; meeting them is the reason this course exists. “Mathematical Induction” and “Strong Induction” name them, so look before then.
Do the recurrence arithmetic by hand once per lesson before using the lab. The lab compares your closed form against the iteration, which is only useful if you produced a closed form to compare.
What it does not cover
Transfinite induction and induction over ordinals. Everything here is induction over ℕ or over a well-founded recursive structure.
Generating functions as a recurrence-solving technique. “Generating Functions” in Combinatorics and Counting introduces them for counting; using them to solve recurrences is a natural next step this path does not take.
Formal verification tools. “Loop Invariants and Program Correctness” writes loop invariants as mathematics, not as annotations a checker consumes.