Proof by induction · 数学归纳法证明
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| positive integer/ˈpɒzɪtɪv ˈɪntɪdʒə/ | 正整数 | zhèng zhěng shù |
| mathematical induction/ˌmæθɪˈmætɪkl ɪnˈdʌkʃn/ | 数学归纳法 | shù xué guī nà fǎ |
| base case/beɪs keɪs/ | 基础情形 | jī chǔ qíng xíng |
| inductive step/ɪnˈdʌktɪv step/ | 归纳步骤 | guī nà bù zhòu |
| conjecture/kənˈdʒektʃə/ | 猜想 | cāi xiǎng |
| divisible/dɪˈvɪzɪbl/ | 整除 | 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.
多米诺证明
- 你如何证明某事对每一个正整数为真——无穷多种情况?
- 数学归纳法(mathematical induction)像多米诺骨牌一样工作:推倒第一块(基本情形),并证明每块骨牌推倒下一块(归纳步骤)。如果两者都成立,它们就全倒下。
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
归纳的两个步骤
- 数学归纳法用两步对每个正整数 $n$ 证明一个结果:
- 基本情形(base case):证明它对 $n = 1$ 为真。
- 归纳步骤(inductive step):假设它对 $n = k$ 为真,然后对 $n = k + 1$ 证明它。
算例。 证明 $\sum_{r=1}^{n} r = \dfrac{n(n+1)}{2}$。 基本情形($n=1$):LHS $= 1$,RHS $= \dfrac{1(2)}{2} = 1$。✓ 归纳步骤:假设对 $n = k$ 为真。对 $n = k+1$: $\sum_{r=1}^{k+1} r = \dfrac{k(k+1)}{2} + (k+1) = \dfrac{(k+1)(k+2)}{2}$。✓
数学归纳法的原理像一连串倒下的多米诺骨牌
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. · 归纳法需要一个基础步骤以及从 k 到 k+1 的归纳步骤。
The base case usually shows the result is true for: · 基础步骤通常表明结果适用于：
The base case checks the smallest value, usually n = 1. · 基础步骤检查最小值，通常是 n = 1。
If both the base case and the inductive step hold, the result is true for all positive integers n. · 如果基础步骤和归纳步骤都成立，则结果对所有正整数 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$.
先猜想再证明
- 常常你从几种情况做一个猜想(conjecture,一个合理的猜测),然后通过归纳证明确认它。
- 例子:$1 + 3 + 5 + 7 = 16 = 4^2$。猜想:前 $n$ 个奇数的和是 $n^2$。
Using induction, the sum 1 + 2 + ... + n = n(n+1)/2. For n = 10, find the sum. · 利用归纳法，求和 1 + 2 + ... + n = n(n+1)/2。当 n = 10 时，求该和。
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. ✓
用归纳证明整除性
- 证明 $3^n - 1$ 对所有正整数 $n$ 能被 $2$ 整除。
- 基本情形($n=1$):$3^1 - 1 = 2$,能被 $2$ 整除。✓
- 归纳步骤:$3^{k+1} - 1 = 3 \cdot 3^k - 1 = 3(3^k - 1) + 2$。因为 $3^k - 1$(由假设)能被 $2$ 整除,整个表达式也能。✓
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
你掌握了
- 归纳 = 基本情形($n=1$)+ 归纳步骤($n=k \Rightarrow n=k+1$)
- 两步合在一起对所有正整数证明它
- 常常从几种情况猜想,然后用归纳证明