Induction and recursion
Đã giới thiệu| English | Ý nghĩa |
|---|---|
| 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.
Độ khó 3/5 · 200 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Độ khó 2/5 · 140 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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!?
Độ khó 2/5 · 140 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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 —
Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay
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.