Proof by induction
| English | Chinese | Pinyin |
|---|---|---|
| positive integer | 正整数 | zhèng zhěng shù |
| mathematical induction | 数学归纳法 | shù xué guī nà fǎ |
| base case | 基础情形 | jī chǔ qíng xíng |
| inductive step | 归纳步骤 | guī nà bù zhòu |
| conjecture | 猜想 | cāi xiǎng |
| divisible | 整除 | zhěng chú |
The domino proof
- How do you prove something is true for every positive integer 正整数 — infinitely many cases?
- Mathematical induction 数学归纳法 works like dominoes: knock over the first one (base case 基础情形), and show each domino knocks over the next (inductive step 归纳步骤). If both work, they all fall.
Proof by induction route
See induction as a first domino plus a rule that pushes every next case.
The two steps of induction
- Mathematical induction proves a result for every positive integer $n$ in two steps:
- Base case: show it's true for $n = 1$.
- Inductive step: assume it's true for $n = k$, then prove it for $n = k + 1$.
Worked example. Prove $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$. Base case ($n=1$): LHS $= 1$, RHS $= \dfrac{1(2)}{2} = 1$. ✓ Inductive step: Assume true for $n = k$. For $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$. ✓
Proof by induction works like a chain of falling dominoes
The two steps of proof by induction are the base case and the:
Induction needs a base case plus an inductive step from k to k+1.
The base case usually shows the result is true for:
The base case checks the smallest value, usually n = 1.
If both the base case and the inductive step hold, the result is true for all positive integers n.
That is exactly what the principle of induction guarantees.
Why both steps are essential
- The base case starts the chain. Without it, you could "prove" false statements.
- The inductive step extends it. Without it, you've only proved one case.
Both steps are essential. A proof with only the inductive step is like a row of dominoes that nobody pushes — they never start falling. A proof with only the base case is like pushing one domino — only one falls.
You can prove a result by induction using only the inductive step, without a base case.
Both steps are essential. Without the base case, the chain never starts.
Conjecture 猜想 then prove
- Often you make a conjecture (a sensible guess) from a few cases, then confirm it by inductive proof.
- Example: $1 + 3 + 5 + 7 = 16 = 4^2$. Conjecture: the sum of the first $n$ odd numbers is $n^2$.
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum.
10(11)/2 = 55.
Induction for divisibility
- Prove $3^n - 1$ is divisible 整除 by $2$ for all positive integers $n$.
- Base case ($n=1$): $3^1 - 1 = 2$, divisible by $2$. ✓
- Inductive step: $3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$. Since $3^k - 1$ is divisible by $2$ (by assumption), so is the whole expression. ✓
In mathematics, a conjecture is:
A conjecture is an unproven statement based on evidence — you then try to prove it (often by induction).
You've got it
- induction = base case ($n=1$) + inductive step ($n=k \Rightarrow n=k+1$)
- both steps together prove it for all positive integers
- often conjecture from cases, then prove by induction