Proof by induction
แนะนำใหม่| English | ความหมาย |
|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | จำนวนเต็มบวก |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | การพิสูจน์โดยอุปนัยทางคณิตศาสตร์ |
| base case/beɪs keɪs/ | กรณีพื้นฐาน |
| inductive step/ɪnˈdʌktɪv step/ | ขั้นตอนอุปนัย |
| conjecture/kənˈdʒektʃə/ | ข้อสันนิษฐาน |
| divisible/dɪˈvɪzɪbl/ | หารลงตัว |
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:
ความยาก 1/5 · 100 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
Induction needs a base case plus an inductive step from k to k+1.
The base case usually shows the result is true for:
ความยาก 1/5 · 100 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
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.
ความยาก 1/5 · 100 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
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.
ความยาก 1/5 · 100 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
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.
ความยาก 2/5 · 140 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
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:
ความยาก 1/5 · 100 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
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
Write from a sum of 36
- The sum of the first n integers is n times (n plus 1) divided by 2.
- Find the sum for n = 8. An induction proof needs a base case and an inductive step.
Using the formula for the sum of the first n integers, what is the sum when n = 8, and why is the inductive step not enough on its own?
The closed formula gives the sum directly. Induction still has to anchor that formula with a first true case.
What is the sum of the first 8 integers?
ความยาก 1/5 · 100 เหรียญ + โบนัสเล็กน้อยในการทำครั้งแรกวันนี้
8 times 9 divided by 2 is 36. Other options — 55 (the lesson sum for n = 10); 8 (the value of n).