Phase 1 - Lesson 1.4

Mathematical Induction and Recursion

Proving infinitely many statements with two steps, and the recursive definitions that induction is built to reason about.

⏱ 50 min● Beginner🔗 Prereqs: 1.3

↖ Phase 1 hub

Builds on: 1.3 gave the core proof templates; induction is the specialized template for statements indexed by the natural numbers.
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.

\[\big[P(1)\ \wedge\ \forall k\,(P(k)\Rightarrow P(k+1))\big]\ \Rightarrow\ \forall n\ge 1\ P(n)\] (1.4)

Worked Example - Sum of the first n integers

Claim \(P(n): \sum_{i=1}^n i=\tfrac{n(n+1)}{2}\). Base: \(P(1)\) gives \(1=\tfrac{1\cdot2}{2}=1\). ✓

Assume \(P(k)\): \(\sum_{i=1}^k i=\tfrac{k(k+1)}{2}\).

Then \(\sum_{i=1}^{k+1} i=\tfrac{k(k+1)}{2}+(k+1)=(k+1)\tfrac{k+2}{2}\), which is \(P(k+1)\). □

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

Common Mistakes to Avoid

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.

Quant Practitioner Tips

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

Q1 Easy

An induction argument with a correct inductive step but NO verified base case proves:

the statement for all n

the statement for no n in general

only the base case

the contrapositive

Q2 Medium

Strong induction differs from weak induction in that the inductive hypothesis assumes:

only P(k)

P(k+1) directly

P(j) for all j from the base up to k

nothing

Q3 Medium

For proving every integer n≥2 has a prime factorization, the natural technique is:

weak induction

strong induction

a single counterexample

direct computation only

Practical Exercise

Prove by induction that \(\sum_{i=1}^{n} i^2=\tfrac{n(n+1)(2n+1)}{6}\) for all \(n\ge 1\).

▶ Show full solution

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

\[\sum_{i=1}^{k+1} i^2=\frac{k(k+1)(2k+1)}{6}+(k+1)^2=\frac{(k+1)\big[k(2k+1)+6(k+1)\big]}{6}=\frac{(k+1)(k+2)(2k+3)}{6},\]

which is the formula with \(n=k+1\) (since \(2(k+1)+1=2k+3\)). By induction it holds for all \(n\ge1\). □

After the reveal, answer for yourself: The algebra hinges on factoring out (k+1). Spotting the common factor is the recurring trick in sum-induction proofs.

Lesson Summary

Induction proves a statement for all naturals from a base case and an inductive step; strong induction strengthens the hypothesis to all smaller cases for recurrences that need them. Recursive definitions mirror the inductive step exactly, so a computable recurrence is both a definition and a numerical check on a proved closed form.

Formula Sheet Additions

Sum of squares

\[\sum_{i=1}^n i^2=\tfrac{n(n+1)(2n+1)}{6}\]

A standard closed form, proved by induction and reused in variance calculations.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: What two ingredients does a valid induction proof require, and what goes wrong if the base case is missing?
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.

Q: When is strong induction necessary rather than weak?
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

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Vol. I, I 4.2-4.3 - The induction principle and its use to prove summation formulas and inequalities.
Make It Stick (Brown, Roediger & McDaniel, 2014) foundational - generation effect - Generation and self-testing: proving then numerically checking a closed form as retrieval practice.

← 1.3 Next: 1.5 →