Induction and recursion
Introduced| English | Meaning |
|---|---|
| induction/ɪnˈdʌkʃn/ | A method of proof that establishes a starting case and shows that truth for one case implies truth for the next. |
| base case/beɪs keɪs/ | An initial case proved directly in an induction argument, or a simple case that ends a recursive process. |
| inductive step/ɪnˈdʌktɪv step/ | inductive step |
| induction hypothesis | induction hypothesis |
| strong induction | strong induction |
| recursive definition | recursive definition |
A loop you can trust for every n
- A loop adds $1 + 2 + \dots + n$. You test $n = 1, 2, 3$ and it matches $\frac{n(n+1)}{2}$. But a test only covers the cases you ran; what about $n = 10^9$?
- Induction 数学归纳法 proves a claim for every $n$ at once. It is how loops and recursive code are proved correct.
The ladder: base and step
- To prove $P(n)$ for all $n \ge n_0$: check the base case 基础情形 $P(n_0)$ by hand. Then prove the inductive step 归纳步骤: if $P(k)$ holds, then $P(k+1)$ holds.
- In the step, $P(k)$ is the induction hypothesis 归纳假设. Base plus step reach every rung: $P(n_0)$ gives $P(n_0 + 1)$, which gives $P(n_0 + 2)$, and so on.
Put the parts of an induction proof in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
The claim, then the first rung, then one climb that works from any rung, then the conclusion.
Proving the sum formula
Claim: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ for all $n \ge 1$.
Base, $n = 1$: the left side is 1 and the right side is $\frac{1 \cdot 2}{2} = 1$ ✓.
Step: assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$. Then
which is the formula at $n = k + 1$ ✓.
- Mark the line where the hypothesis is used. A step that never uses $P(k)$ has proved nothing about the chain.
In the step for Σi = n(n+1)/2, the sum up to k + 1 is rewritten as —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Split off the last term: the hypothesis covers 1 to k, then add k + 1. Only after simplifying do you reach (k+1)(k+2)/2.
Use the formula to find 1 + 2 + … + 100.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
100 × 101 ÷ 2 = 5050.
Strong induction
- Strong induction 强归纳法 assumes $P(n_0), \dots, P(k)$, every rung below, not just $P(k)$. Use it when $k + 1$ depends on a case further down.
- Example: every integer $n \ge 2$ is a product of primes. If $k + 1$ is not prime, $k + 1 = ab$ with $2 \le a, b \le k$, and both $a$ and $b$ are covered by the hypothesis.
Proving that every n ≥ 2 is a product of primes needs strong induction, because k + 1 = ab depends on cases below k.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The factors a and b can be any size from 2 to k, so the hypothesis must cover every rung below, not just k.
Recursion is induction built downwards
- A recursive definition 递归定义 gives a base value and a rule using smaller cases: $0! = 1$ and $n! = n \cdot (n-1)!$. It is the same ladder, built instead of climbed.
- To prove a recursive function correct, induct on the input size: the base case of the code is the base case of the proof, and the recursive call is the hypothesis.
Using 0! = 1 and n! = n · (n−1)!, what is 5!?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
5 × 4 × 3 × 2 × 1 × 1 = 120; the recursion stops at the base value 0! = 1.
Catching a faulty proof
- "All horses are the same colour." The step removes a different horse from a group of $k + 1$ to get two groups of $k$ that overlap, so all must match.
- At $k + 1 = 2$ the two groups are single horses with nothing in common. The step silently needs $k \ge 2$, and $P(2)$ was never proved, so the chain breaks there.
The "all horses are the same colour" proof fails because —
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The step needs an overlapping horse, which exists only when k ≥ 2; P(2) was never proved.
Marks that slip away
- No base case. Hypothesis plus step with no first rung is a ladder standing on air.
- Hypothesis never used. Write "by the hypothesis" at the exact line.
- Assuming $P(k+1)$. Using the goal to prove itself is circular.
- Step that fails for small $k$. Check the smallest case the step must cover.
You've got it
- Induction = base case $P(n_0)$ + step $P(k) \Rightarrow P(k+1)$, with the hypothesis used.
- Strong induction assumes every rung below $k + 1$.
- Recursion defines downwards; proving recursive code correct is induction on input size.