Learning objectives
By the end of this week you can:
- 1 Write complete proofs by mathematical induction and strong induction.
- 2 Define sets, sequences and functions recursively.
- 3 Prove properties of recursive definitions by structural induction.
- 4 Use Big-O, Big-Ω and Big-Θ to compare growth rates.
- 5 Connect loop invariants to induction when reasoning about code.
★ the wow moment
Induction is how you know your recursive code works.
If the base case is right and each call is right assuming the smaller calls are right, the whole function is right. That sentence is a proof by induction, and it is how you should read every recursive function you write.
Topics
- Mathematical induction
- Strong induction and well-ordering
- Recursive definitions and structural induction
- Recursive algorithms
- Big-O, Big-Ω, Big-Θ
Before class
- Skim Rosen 5.1–5.3, 3.2 (20 minutes is enough; we go through it together).
- Bring paper and a pen: part of every lecture is solving by hand.
In industry
-
Loop invariants
Correctness arguments for loops (binary search, sorting) are induction on the number of iterations.
-
Performance
Big-O decides whether a feature survives a million users: O(n²) that is fine at 1,000 users can fail at 1,000,000.
-
Parsers and compilers
Grammars are recursive definitions; compilers process programs by structural recursion.
Lab 10: Recursion and Growth
Write recursive functions, check them against induction proofs, and measure running times to see Big-O on a plot.
due Fri, Dec 11 · 23:59 · 100 points · opens in week 12
Go deeper
- Mathematics for Computer Science (Lehman, Leighton, Meyer) · Chapter 5, induction
- Book of Proof (Richard Hammack) · Chapter 10, induction
- MIT 6.042J video lectures (OpenCourseWare) · induction lectures
Tags:inductionstrong inductionrecursionBig-Ogrowthloop invariant