Mathematical Induction and Recursion
Proving infinitely many statements with two steps, and the recursive definitions that induction is built to reason about.
Leads to: Recursion and induction underlie dynamic programming, tree pricing (Phase 14), and convergence proofs for numerical schemes.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- State and apply the principle of weak induction: base case plus inductive step.
- Use strong induction when the step needs several previous cases.
- Define sequences recursively and connect the definition to an inductive proof of a closed form.
- Implement a recursive computation and validate it against its proved closed form.
Key Vocabulary
- Weak (ordinary) induction
- Prove P(1), then P(k)⇒P(k+1); conclude P(n) for all n≥1.
- Strong induction
- Assume P holds for all values up to k to prove P(k+1); equivalent in power to weak induction.
- Base case
- The smallest instance you verify directly; without it the whole argument collapses.
- Inductive hypothesis
- The assumed truth of P(k) (or all j≤k) used to establish the next case.
- Recursive definition
- A definition of a_n in terms of earlier terms plus explicit initial values.
- Closed form
- A non-recursive formula giving a_n directly from n.
The principle
To prove a statement \(P(n)\) for every natural number, you need only two things: a base case \(P(1)\) and an inductive step \(P(k)\Rightarrow P(k+1)\). Like dominoes: knock the first, and guarantee each knocks the next.
Strong induction
Sometimes \(P(k+1)\) needs more than the single previous case. Strong induction assumes \(P(1),\dots,P(k)\) all hold. It proves, for instance, that every integer \(n\ge 2\) has a prime factorization: either \(n\) is prime, or \(n=ab\) with \(a,b\lt n\), and both factor by the (strong) hypothesis.
Recursion: definitions that call themselves
A recursive definition gives initial terms and a rule producing later ones. The Fibonacci numbers \(F_1=F_2=1,\ F_n=F_{n-1}+F_{n-2}\) are the canonical example. Induction is the natural tool to prove properties of recursively defined objects because the recurrence is an inductive step.
Interactive: recursion meets its closed form
- Skipping or fudging the base case; a valid inductive step with no base proves nothing (you can ‘prove’ all numbers are equal that way).
- Assuming what you want to prove: the inductive hypothesis is P(k), not P(k+1).
- Using weak induction when the step genuinely needs several earlier cases - switch to strong induction.
- Off-by-one errors in the base index (starting at 0 vs 1) that break the chain.
- Always write the base case explicitly and check it - it is where sneaky errors hide.
- State the inductive hypothesis in a labeled line so the reader sees exactly what you assumed.
- If P(k+1) refers to two or more earlier terms (like Fibonacci), reach for strong induction.
- A recurrence you can compute is a free test harness for a closed form you claim to have proved.
Knowledge Check
Practical Exercise
Prove by induction that \(\sum_{i=1}^{n} i^2=\tfrac{n(n+1)(2n+1)}{6}\) for all \(n\ge 1\).
Base. \(n=1\): left side \(=1\), right side \(=\tfrac{1\cdot2\cdot3}{6}=1\). ✓
Step. Assume \(\sum_{i=1}^{k} i^2=\tfrac{k(k+1)(2k+1)}{6}\). Then
which is the formula with \(n=k+1\) (since \(2(k+1)+1=2k+3\)). By induction it holds for all \(n\ge1\). □
Lesson Summary
Formula Sheet Additions
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: A verified base case and an inductive step P(k)⇒P(k+1); without the base case the chain never starts, so nothing is proved - you can even ‘prove’ false universals.
A: When establishing P(k+1) requires assuming several earlier cases (e.g. n=ab with a,b
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check