Mathematical Induction: A Comprehensive Guide | 数学归纳法原理详解

📚 Mathematical Induction: A Comprehensive Guide | 数学归纳法原理详解

Mathematical induction is one of the most elegant and powerful proof techniques in mathematics, especially within the IB Mathematics curriculum. It allows us to prove statements that depend on a natural number n, such as formulas, inequalities, and divisibility properties, with a surprisingly simple yet rigorous structure.

数学归纳法是数学中最优雅且强大的证明技巧之一，尤其在 IB 数学课程中占有重要地位。它使我们能够证明依赖于自然数 n 的命题，例如公式、不等式和整除性质，其结构既简洁又严谨。

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

Imagine an infinite row of dominoes. If you push the first domino, and each domino, when it falls, knocks over the next one, then all dominoes will fall. Mathematical induction is the mathematical version of this idea: we verify that the statement holds for the “first” case, and then prove that if it holds for some arbitrary case, it must also hold for the next case.

想象一排无限长的多米诺骨牌。如果你推倒第一块，且每一块倒下时都会撞倒下一块，那么整排骨牌都会倒下。数学归纳法正是这一思想的数学表达：我们先验证命题对“第一个”情况成立，然后证明若命题对某一任意情况成立，则它必然对下一个情况也成立。

If P(1) is true, and for every k ≥ 1, P(k) ⇒ P(k+1), then P(n) is true for all n ∈ ℕ.

若 P(1) 为真，且对所有 k ≥ 1，P(k) ⇒ P(k+1)，则 P(n) 对所有 n ∈ ℕ 为真。

2. The Two Essential Steps | 两个必要步骤

A proof by induction always consists of two distinct parts: the base case and the inductive step. Without either one, the proof is incomplete.

归纳证明总是包含两个截然不同的部分：基础情形和归纳步骤。缺少其中任何一部分，证明都是不完整的。

Base Case: Prove that the statement holds for the smallest value, usually n = 1 or n = 0.

基础情形：证明命题对最小值成立，通常是 n = 1 或 n = 0。
Inductive Step: Assume the statement holds for some arbitrary n = k (this is the inductive hypothesis), and then prove it holds for n = k+1.

归纳步骤：假设命题对某个任意 n = k 成立（这就是归纳假设），然后证明它对 n = k+1 也成立。

3. Example: Sum of the First n Natural Numbers | 示例：前 n 个自然数的和

Let us prove the classic formula for the sum of the first n natural numbers:

让我们证明前 n 个自然数之和的经典公式：

1 + 2 + 3 + ⋯ + n = n(n+1)/2

Base Case: For n = 1, the left-hand side is 1, and the right-hand side is 1(1+1)/2 = 1. Thus the formula holds.

基础情形：当 n = 1 时，左边为 1，右边为 1(1+1)/2 = 1。因此公式成立。

Inductive Hypothesis: Assume that for some arbitrary k ≥ 1, the formula holds:

归纳假设：假设对某个任意 k ≥ 1，公式成立：

1 + 2 + 3 + ⋯ + k = k(k+1)/2

Inductive Step: We need to show that the formula holds for k+1:

归纳步骤：我们需要证明公式对 k+1 也成立：

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

Starting from the left-hand side and using the inductive hypothesis:

从左边出发，利用归纳假设：

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

Therefore, the formula holds for k+1. By induction, the formula is true for all n ∈ ℕ.

因此，公式对 k+1 成立。由归纳法可知，该公式对所有 n ∈ ℕ 成立。

4. Proving Divisibility | 证明整除性

Induction is frequently used to prove that an expression is divisible by a certain number for all natural n.

归纳法常被用来证明某个表达式对所有自然数 n 都能被某个数整除。

Consider the statement: “n³ + 2n is divisible by 3 for all n ∈ ℕ.”

考虑命题：“对所有 n ∈ ℕ，n³ + 2n 能被 3 整除。”

Base Case: For n = 1, 1³ + 2(1) = 3, which is divisible by 3.

基础情形：当 n = 1 时，1³ + 2(1) = 3，能被 3 整除。

Inductive Hypothesis: Assume 3 divides k³ + 2k, i.e., k³ + 2k = 3m for some integer m.

归纳假设：假设 3 整除 k³ + 2k，即 k³ + 2k = 3m，其中 m 为整数。

Inductive Step: Consider (k+1)³ + 2(k+1):

归纳步骤：考虑 (k+1)³ + 2(k+1)：

(k+1)³ + 2(k+1) = k³ + 3k² + 3k + 1 + 2k + 2 = (k³ + 2k) + 3(k² + k + 1)

By the inductive hypothesis, k³ + 2k is a multiple of 3, and 3(k² + k + 1) is clearly a multiple of 3. Hence the sum is divisible by 3. This completes the induction.

由归纳假设，k³ + 2k 是 3 的倍数，而 3(k² + k + 1) 显然也是 3 的倍数。因此它们的和能被 3 整除。归纳完成。

5. Proving Inequalities | 证明不等式

Induction is also a powerful tool for proving inequalities, especially those involving powers and factorials.

归纳法同样是证明不等式的有力工具，尤其是涉及幂和阶乘的不等式。

Example: Prove that 2ⁿ > n for all n ≥ 1.

示例：证明对所有 n ≥ 1，2ⁿ > n 成立。

Base Case: For n = 1, 2¹ = 2 > 1, which is true.

基础情形：当 n = 1 时，2¹ = 2 > 1，成立。

Inductive Hypothesis: Assume 2ᵏ > k for some k ≥ 1.

归纳假设：假设对某个 k ≥ 1，2ᵏ > k 成立。

Inductive Step: For k+1, we want to show 2ᵏ⁺¹ > k+1.

归纳步骤：对于 k+1，我们要证明 2ᵏ⁺¹ > k+1。

2ᵏ⁺¹ = 2 × 2ᵏ > 2k = k + k ≥ k + 1

Since k ≥ 1, we have 2k ≥ k+1. Thus 2ᵏ⁺¹ > k+1, and the proof is complete.

由于 k ≥ 1，我们有 2k ≥ k+1。因此 2ᵏ⁺¹ > k+1，证明完成。

6. Recursive Sequences and Induction | 递推数列与归纳法

When a sequence is defined recursively, induction is often the natural method to prove an explicit formula or a property of the sequence.

当一个数列以递推方式定义时，归纳法往往是证明其通项公式或性质的天然方法。

Consider the sequence defined by uₙ₊₁ = 2uₙ + 1, with u₁ = 1. We will prove that uₙ = 2ⁿ − 1.

考虑由 uₙ₊₁ = 2uₙ + 1 定义且 u₁ = 1 的数列。我们将证明 uₙ = 2ⁿ − 1。

Base Case: For n = 1, u₁ = 1 = 2¹ − 1, which is true.

基础情形：当 n = 1 时，u₁ = 1 = 2¹ − 1，成立。

Inductive Hypothesis: Assume uₖ = 2ᵏ − 1.

归纳假设：假设 uₖ = 2ᵏ − 1。

Inductive Step: Using the recursive definition:

归纳步骤：利用递推定义：

uₖ₊₁ = 2uₖ + 1 = 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 2 + 1 = 2ᵏ⁺¹ − 1

Thus the explicit formula holds for k+1. By induction, uₙ = 2ⁿ − 1 for all n ∈ ℕ.

因此通项公式对 k+1 成立。由归纳法，对所有 n ∈ ℕ，uₙ = 2ⁿ − 1。

7. Strong Induction | 强归纳法

In some cases, assuming that P(k) is true is not enough; we may need to assume that P(1), P(2), …, P(k) are all true. This is called strong induction, and it is particularly useful for properties involving prime factorisation or Fibonacci-type sequences.

在某些情况下，仅假设 P(k) 成立是不够的；我们可能需要假设 P(1), P(2), …, P(k) 全部成立。这称为强归纳法，在涉及质因数分解或斐波那契型数列的性质时尤其有用。

If P(1) is true, and for every k ≥ 1, [P(1) ∧ P(2) ∧ ⋯ ∧ P(k)] ⇒ P(k+1), then P(n) holds for all n ∈ ℕ.

若 P(1) 为真，且对所有 k ≥ 1，[P(1) ∧ P(2) ∧ ⋯ ∧ P(k)] ⇒ P(k+1)，则 P(n) 对所有 n ∈ ℕ 成立。

Strong induction does not require a separate base case in the same way as ordinary induction, but it is still essential to verify the first few cases explicitly to anchor the argument.

强归纳法与普通归纳法不同，不一定需要单独的基础情形，但显式验证初始几个情形仍然是必要的，以便锚定论证。

8. Common Mistakes to Avoid | 常见错误

Induction proofs are often graded harshly when key elements are missing. Here are the most common pitfalls.

归纳证明在评分时常因缺少关键要素而失分。以下是最常见的陷阱。

Skipping the base case: Without verifying the base case, the inductive step alone is meaningless.

跳过基础情形：如果不验证基础情形，仅凭归纳步骤是毫无意义的。
Using the inductive hypothesis incorrectly: You must clearly state when and how you are applying the assumption P(k).

错误使用归纳假设：你必须明确说明在何时以及如何应用假设 P(k)。
Proving P(k) from P(k+1): The induction step must go forward, never backward.

用 P(k+1) 证明 P(k)：归纳步骤必须是向前的，绝不能反向。
Vague conclusion: Always explicitly state that “by the principle of mathematical induction, the statement is true for all n ∈ ℕ.”

结论含糊：务必明确写出“根据数学归纳法原理，该命题对所有 n ∈ ℕ 成立”。

9. IB Examination Tips | IB 考试提分要点

In IB Mathematics Analysis and Approaches (AA), induction appears in Paper 1 or Paper 2, often as a 6–8 mark question. The marking scheme typically rewards clarity and logical structure.

在 IB 数学分析与方法（AA）中，归纳法出现在 Paper 1 或 Paper 2，通常为 6–8 分。评分标准通常看重清晰度和逻辑结构。

Marking Component	What Examiners Look For
Base case	Correct value, usually n=1 or n=0, explicitly verified.
Inductive hypothesis	Clear statement of the assumption for n=k.
Inductive step	Algebraic manipulation that clearly uses P(k) to derive P(k+1).
Conclusion	Final statement invoking the principle of induction.

Always write the inductive hypothesis explicitly before using it. Marks are often awarded for the correct statement even if the algebra goes wrong.

在实际使用归纳假设之前，一定要明确写出它。即便后续代数出错，写出正确的归纳假设也常常能获得分数。

10. Why Induction Works: The Well-Ordering Principle | 归纳法为何成立：良序原理

The validity of mathematical induction rests on a fundamental property of the natural numbers: every non-empty set of natural numbers has a least element. This is called the Well-Ordering Principle.

数学归纳法的有效性建立在自然数的一个基本性质之上：每个非空自然数集合都有一个最小元素。这就是良序原理。

To see why induction follows, suppose P(1) is true and P(k) ⇒ P(k+1) for all k. If there were some n for which P(n) is false, the set of such counterexamples would have a smallest element m. Since P(1) is true, m > 1. Then P(m−1) must be true, because otherwise m−1 would be a smaller counterexample. But by the inductive step, P(m−1) implies P(m), contradicting the fact that m is a counterexample.

为了理解归纳法为何成立，假设 P(1) 为真且对所有 k，P(k) ⇒ P(k+1)。如果存在某个 n 使 P(n) 为假，那么这些反例构成的集合必有一个最小元素 m。由于 P(1) 为真，m > 1。那么 P(m−1) 必然为真，否则 m−1 将是更小的反例。但由归纳步骤，P(m−1) 推出 P(m)，这与 m 是反例矛盾。

11. Summary | 总结

Mathematical induction is a cornerstone of IB Mathematics. Mastering it requires understanding the logical structure: base case, inductive hypothesis, inductive step, and conclusion. With practice, you will recognise induction problems quickly and execute the proof with confidence.

数学归纳法是 IB 数学的基石。掌握它需要理解其逻辑结构：基础情形、归纳假设、归纳步骤与结论。通过练习，你将能快速识别归纳法问题并自信地完成证明。

Remember: induction is not a “guess” or a “shortcut”. It is a rigorous, axiomatically supported method of proof that works for statements indexed by natural numbers.

请记住：归纳法不是“猜测”或“捷径”。它是一种严谨的、有公理基础支持的证明方法，适用于以自然数编号的命题。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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

Mathematical Induction: A Comprehensive Guide | 数学归纳法原理详解