Mastering Proof by Mathematical Induction | 掌握数学归纳法

📚 Mastering Proof by Mathematical Induction | 掌握数学归纳法

Proof by mathematical induction is one of the cornerstones of the IB Mathematics: Analysis and Approaches Higher Level syllabus, and it reappears in A Level Further Mathematics, in STEP and MAT preparation, and in every rigorous pre-university course that touches number theory. Mastering the technique does more than let you prove statements about sums, inequalities, divisibility and recurrence relations: it trains the kind of precise, structural logical thinking that all later mathematics demands. Think of a line of dominoes. If you can topple the first one, and you can guarantee that each falling domino knocks over the next, then the entire line must fall, no matter how long it is. This article covers the core principle, the formal logic behind it, a reusable four-step template, worked examples across every common question type, strong induction and other variants, the errors examiners see most often, and exam-focused strategy with a final checklist.

数学归纳法是 IB 数学分析与方法（HL）课程的基石之一，同时也出现在 A Level 进阶数学、STEP 与 MAT 备考，以及所有涉及数论的严谨预科课程中。掌握这一技巧不仅能让你证明关于求和、不等式、整除性和递推关系的命题，更能训练此后一切数学都需要的精确而结构化的逻辑思维。想象一排多米诺骨牌：只要你能推倒第一张，并能保证每一张倒下的牌都会碰倒下一张，那么无论这排牌有多长，整排都必然倒下。本文将涵盖核心原理、其背后的形式逻辑、可复用的四步模板、覆盖所有常见题型的工作示例、强归纳法及其他变体、考官最常看到的错误，以及以考试为导向的策略与最终检查清单。

---

1. The Principle of Mathematical Induction | 数学归纳法原理

Mathematical induction is a method for proving that a statement P(n) is true for all natural numbers n, or for all integers n greater than or equal to some starting value n₀. A complete proof has exactly two essential parts. Base case: verify that P(n₀) is true, where n₀ is the first value in the domain (usually 1, but sometimes 0, 2 or 5). Inductive step: assume that P(k) is true for an arbitrary value k in the domain - this assumption is called the inductive hypothesis - and then prove that P(k+1) must also be true. If both parts are established, the principle of mathematical induction allows us to conclude that P(n) holds for every n in the domain. The inductive hypothesis is never a claim that the statement is true for all n; it is a single, temporary assumption about one unspecified value k.

数学归纳法是用来证明命题 P(n) 对所有自然数 n（或对所有大于等于某个起始值 n₀ 的整数）都成立的方法。一个完整的证明恰好包含两个关键部分。基础步骤：验证 P(n₀) 成立，其中 n₀ 是定义域中的第一个取值（通常是 1，但有时是 0、2 或 5）。归纳步骤：假设 P(k) 对定义域中某个任意取值 k 成立——这个假设称为归纳假设——然后证明 P(k+1) 也必然成立。若两部分都得以确立，数学归纳法原理就允许我们断定 P(n) 对定义域中每个 n 都成立。归纳假设绝不是"命题对所有 n 成立"这一断言，它只是关于某一个未指定取值 k 的、临时性的单一假设。

[ P(n₀) ∧ ( ∀k ≥ n₀, P(k) → P(k+1) ) ] → ∀n ≥ n₀, P(n)

Read that line carefully: the left-hand bracket contains both obligations you must discharge, and the arrow delivers the conclusion. Many students lose marks simply because they never write the final concluding sentence, even though their algebra is perfect.

请仔细读这一行：左侧方括号里包含你必须完成的两个义务，而箭头给出结论。许多学生明明代数完全正确，却仅仅因为没有写出最后那句结论性语句而失分。

---

2. Why Induction Works | 为什么归纳法有效

The domino analogy is more than decoration. The base case tips the first domino. The inductive step is a guarantee that the gap between any domino and the next is smaller than a domino. Given both, no domino can remain standing, because the first standing domino would have to be preceded by a fallen one that failed to tip it - contradicting the inductive step. The formal justification rests on the well-ordering property of the natural numbers: every non-empty set of positive integers has a least element. Suppose a statement passed both tests but failed for some n. Then there would be a least failing value m, and by minimality m − 1 would satisfy the statement, so the inductive step would force m to satisfy it as well - a contradiction.

多米诺类比不只是装饰。基础步骤推倒第一张牌；归纳步骤保证任意一张牌与下一张牌之间的间距小于一张牌的长度。两者兼备，就没有任何一张牌能立着不倒，因为若真有第一张未倒的牌，它前面那张已倒的牌就必然没能碰倒它——这与归纳步骤矛盾。形式化的依据来自自然数的良序性质：任何非空的正整数集合都有最小元素。假设某命题通过了这两项检验，却对某个 n 不成立，那么就存在最小的失败取值 m；由最小性，m − 1 满足该命题，于是归纳步骤又会迫使 m 也满足它——矛盾。

its own. A statement can have a valid base case but fail the inductive step, as with P(n): "n² + n + 41 is prime" osite. Conversely, a statement can have a valid inductive step but fail at the base: P(n): "n = n + 1" would "propagate" lse at n = 1, so it is simply false everywhere. Exam questions exploit exactly these gaps.

这也解释了为什么两个部分各自都不可或缺。一个命题可以有有效的基础步骤却通不过归纳步骤，例如 P(n)："n² + n + 41 是质数"。它对 n = 0, 1, 2, … 一直到 n = 39 都成立，但在 n = 40 时该式等于 40² + 40 + 41 = 1681 = 41²，是合数。反过来，一个命题可以有有效的归纳步骤却栽在基础上：P(n)："n = n + 1" 若曾成立就会平凡地"传播"下去，但它在 n = 1 处为假，因此处处为假。考题恰恰会利用这两个缺口。

---

3. The Four-Step Template | 四步模板

Nearly every induction answer you write in an examination should follow the same visible structure. Examiners mark the structure as well as the algebra, so make the four stages explicit with headings or labelled sentences. The table below summarises what each stage must contain and the sentence that signals it.

你在考试中书写的几乎每一个归纳法答案都应遵循同一套清晰可见的结构。考官既评分结构也评分代数，因此请用小标题或标号句把四个阶段明确写出。下表总结了每个阶段必须包含的内容以及标示它的句子。

Stage	What to write	Signalling sentence
1. Statement	Define P(n) precisely, including the domain n ≥ n₀.	"Let P(n) be the statement that ... for n ≥ 1."
2. Base case	Substitute n = n₀ and verify both sides agree numerically.	"For n = 1: LHS = ..., RHS = ..., so P(1) is true."
3. Inductive step	Assume P(k), state the hypothesis, then manipulate the k+1 case until it matches P(k+1).	"Assume P(k) is true for some k ≥ 1, i.e. ..."
4. Conclusion	Name the principle and state the domain.	"Hence by mathematical induction, P(n) is true for all n ≥ 1."

A useful habit is to write the target of the inductive step before you start the algebra: "we must show that ... ". This keeps you honest, because at the end you can check your final line against the target you wrote down. In an IB Paper 3 or A Level Further Mathematics answer, that target line is itself worth a method mark.

一个有用的习惯是：在动笔做代数之前，先把归纳步骤的目标写出来——"我们需要证明……"。这样你就不会跑偏，因为最后可以把结果与先前写下的目标逐字核对。在 IB 第三卷或 A Level 进阶数学的答案中，这行目标本身就是一个方法分。

---

4. Worked Example 1: Summation Formulas | 示例一：求和公式

+1)/2. This is the archetypal induction question and the model on which all later summation proofs are built.

命题：对所有 n ≥ 1，1 + 2 + 3 + … + n = n(n+1)/2。这是最典型的归纳法题目，也是此后所有求和证明所依循的范本。

Base case (n = 1): ide is 1, and the right-hand side is 1 × (1 + 1)/2 = 1. Both sides agree, so P(1) is true.

基础步骤（n = 1）：左边为 1，右边为 1 × (1 + 1)/2 = 1。两边相等，故 P(1) 成立。

Inductive hypothesis: assume that for some k ≥ 1, 1 + 2 + ... + k = k(k+1)/2.

归纳假设：假设对某个 k ≥ 1，有 1 + 2 + … + k = k(k+1)/2。

Inductive step: k+1)(k+2)/2. Starting from the left and using the hypothesis to replace the whole sum up to k:

归纳步骤：我们需要证明 1 + 2 + … + k + (k+1) = (k+1)(k+2)/2。从左边出发，用归纳假设替换前 k 项之和：

1 + 2 + ... + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k + 2)/2

the implication holds for all k ≥ 1, by mathematical induction P(n) is true for all n ≥ 1.

最后得到的表达式恰好是 (k+1)((k+1) + 1)/2，也就是命题 P(k+1)。因此 P(k) → P(k+1) 成立。由于 P(1) 为真且该蕴含对所有 k ≥ 1 成立，由数学归纳法，P(n) 对所有 n ≥ 1 为真。

---

5. Worked Example 2: Sums of Squares and Cubes | 示例二：平方和与立方和

dentical, but the algebra in the inductive step is heavier, which is exactly why examiners like it.

命题：对所有 n ≥ 1，1² + 2² + 3² + … + n² = n(n+1)(2n+1)/6。结构完全相同，但归纳步骤中的代数更繁重，这正是考官偏爱它的原因。

广告 / Sponsored

Base case (n = 1): left-hand side 1² = 1; right-hand side 1 × 2 × 3/6 = 1. True.

基础步骤（n = 1）：左边 1² = 1；右边 1 × 2 × 3/6 = 1。成立。

Hypothesis: assume 1² + ... + k² = k(k+1)(2k+1)/6 for some k ≥ 1.

归纳假设：假设对某个 k ≥ 1，1² + … + k² = k(k+1)(2k+1)/6。

Step: adding the next square and simplifying over the common denominator 6 gives:

归纳步骤：加上下一项平方，并通分到分母 6，得到：

k(k+1)(2k+1)/6 + (k+1)² = (k+1)[ k(2k+1) + 6(k+1) ] / 6

= (k+1)(2k² + 7k + 6)/6 = (k+1)(k+2)(2k+3)/6

e most marks are lost; practise it until it is automatic. The companion result for cubes, 1³ + 2³ + ... + n³ = [n(n+1)/2]², makes an excellent self-test because the inductive step reduces to a perfect square.

由于 k+2 = (k+1) + 1 且 2k+3 = 2(k+1) + 1，这恰好就是 P(k+1)，归纳完成。因式分解那一步 2k² + 7k + 6 = (k+2)(2k+3) 最容易丢分，请练到自动化为止。配套的立方和结果 1³ + 2³ + … + n³ = [n(n+1)/2]² 是极好的自测题，因为它的归纳步骤最终归结为一个完全平方。

---

6. Worked Example 3: Divisibility Proofs | 示例三：整除性证明

Claim: for all n ≥ 1, 3²ⁿ⁺¹ + 2ⁿ⁺² is divisible by 7. Divisibility questions require one extra move: you must use the hypothesis as an equation rather than merely as a rewritten sum. Say "assume 3^2k+1 + 2^k+2 = 7m for some integer m", then substitute.

命题：对所有 n ≥ 1，3²ⁿ⁺¹ + 2ⁿ⁺² 能被 7 整除。整除性问题需要多走一步：你必须把归纳假设当作一个等式来使用，而不仅仅是改写求和式。要写出"假设存在整数 m 使 3^2k+1 + 2^k+2 = 7m"，然后代入。

Base case (n = 1): 3³ + 2³ = 27 + 8 = 35 = 7 × 5, so divisible by 7.

基础步骤（n = 1）：3³ + 2³ = 27 + 8 = 35 = 7 × 5，能被 7 整除。

Step: et the expression for n = k+1 and split the powers so that the hypothesis can be inserted:

归纳步骤：对准 n = k+1 的表达式，把幂拆开，使归纳假设可以插入：

3^2k+3 + 2^k+3 = 9 × 3^2k+1 + 2 × 2^k+2

= 9(7m − 2^k+2) + 2 × 2^k+2 = 63m − 7 × 2^k+2 = 7(9m − 2^k+2)

lete. A second standard target is 4ⁿ + 6n − 1 divisible by 9; there the hypothesis gives 4^k = 9m − 6k + 1, and the step becomes 4 × 4^k trick: always rewrite the k+1 expression so that the exact k-expression appears inside it.

这是 7 的整数倍，故 P(k+1) 成立，归纳完成。另一个标准命题是 4ⁿ + 6n − 1 能被 9 整除；此时归纳假设给出 4^k = 9m − 6k + 1，归纳步骤变为 4 × 4^k + 6k + 5 = 36m − 18k + 9 = 9(4m − 2k + 1)。请注意这个反复出现的技巧：永远把 k+1 的表达式改写，使那个确切的 k 表达式出现在其中。

---

7. Worked Example 4: Inequalities | 示例四：不等式

equality inductions need an extra comparison, because you cannot simply substitute an equality. The standard pattern is to build a chain of inequalities: start from the k+1 expression, create the k-expression by factoring, apply the hypothesis, then show the remaining factor is large enough.

命题：对所有整数 n ≥ 5，2ⁿ > n²。不等式型归纳需要额外的比较，因为你无法简单地代入一个等式。标准套路是构造不等式链：从 k+1 的表达式出发，通过提取因子造出 k 的表达式，应用归纳假设，再证明剩下的因子足够大。

Base case (n = 5): 2⁵ = 32 and 5² = 25, so 32 > 25, true.

基础步骤（n = 5）：2⁵ = 32，5² = 25，故 32 > 25 成立。

Hypothesis: assume 2^k > k² for some k ≥ 5.

归纳假设：假设对某个 k ≥ 5，有 2^k > k²。

Step: the hypothesis by 2 (a positive number, so the inequality direction is preserved) to get 2^k+1 > 2k². It now suffices to prove 2k² > (k+1)² for k ≥ 5, and indeed:

归纳步骤：将假设两边乘以 2（正数，不等号方向不变），得 2^k+1 > 2k²。于是只需证明当 k ≥ 5 时 2k² > (k+1)²，而事实上

更多咨询请联系16621398022（同微信）