Proof by induction
Introduced| English | Meaning |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | positive integer |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | A proof method establishing a base case and showing that truth for an arbitrary integer implies truth for the next integer. |
| 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 |
| conjecture/kənˈdʒektʃə/ | A mathematical statement proposed as true but not yet established by a proof. |
| divisible/dɪˈvɪzɪbl/ | divisible |
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Induction needs a base case plus an inductive step from k to k+1.
The base case usually shows the result is true for:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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