IB Mathematics: Proof by Mathematical Induction | IB数学：数学归纳法证明技巧

📚 IB Mathematics: Proof by Mathematical Induction | IB数学：数学归纳法证明技巧

Mathematical induction is one of the most elegant and powerful proof techniques in mathematics. For IB students, mastering induction is essential, as it appears frequently in the Analysis and Approaches HL/SL exams, particularly in sequences, divisibility, and inequalities.

数学归纳法是数学中最优雅且最强大的证明技巧之一。对于IB学生而言，掌握归纳法至关重要，因为它经常出现在分析与方法HL/SL考试中，特别是在数列、整除和不等式问题中。

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

Mathematical induction is a method used to prove that a statement P(n) is true for all natural numbers n (or for all integers n ≥ m, where m is a starting point). The idea is analogous to falling dominoes: if the first domino falls, and each domino knocks down the next, then all dominoes will fall.

数学归纳法是一种用于证明命题P(n)对所有自然数n（或所有满足n ≥ m的整数n，其中m为起始点）都成立的方法。其思想类似于多米诺骨牌效应：如果第一张骨牌倒下，且每张骨牌都能推倒下一张，那么所有骨牌都会倒下。

There are two key parts to any proof by induction: the base case and the inductive step. Together, they form a complete proof.

任何归纳证明都由两个关键部分组成：基础情形和归纳步骤。两者合在一起，构成完整的证明。

2. Step-by-Step Structure of Induction | 归纳法的分步结构

To prove a statement P(n) for all n ≥ 1, follow these three steps:

要证明命题P(n)对所有n ≥ 1成立，请遵循以下三个步骤：

Base Case: Verify that P(1) is true.
Inductive Hypothesis: Assume that P(k) is true for some arbitrary positive integer k.
Inductive Step: Using the assumption that P(k) is true, prove that P(k+1) is true.

基础情形：验证P(1)成立。
归纳假设：假设P(k)对某个任意正整数k成立。
归纳步骤：利用P(k)成立的假设，证明P(k+1)成立。

Once these three steps are completed, by the principle of mathematical induction, P(n) is true for all positive integers n.

一旦这三步完成，根据数学归纳法原理，P(n)对所有正整数n都成立。

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

Let us prove that 1 + 2 + 3 + … + n = n(n+1)/2 for all positive integers n.

让我们证明：1 + 2 + 3 + … + n = n(n+1)/2 对所有正整数n成立。

Base Case: For n = 1, the left side is 1, and the right side is 1(1+1)/2 = 1. Hence P(1) is true.

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

Inductive Hypothesis: Assume that for some k ≥ 1, we have 1 + 2 + 3 + … + k = k(k+1)/2.

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

Inductive Step: We need to show that 1 + 2 + 3 + … + k + (k+1) = (k+1)(k+2)/2. Using the hypothesis, we substitute the sum up to k:

归纳步骤：我们需要证明1 + 2 + 3 + … + k + (k+1) = (k+1)(k+2)/2。利用归纳假设，替换前k项的和：

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

Thus P(k+1) is true. By induction, the formula holds for all positive integers n.

因此P(k+1)成立。由归纳法可知，该公式对所有正整数n成立。

4. Induction in Divisibility Problems | 归纳法在整除问题中的应用

Induction is frequently used to prove that an expression is divisible by a given integer. The key is to express the (k+1) case in terms of the k case, often by adding a multiple of the divisor.

归纳法常用于证明某个表达式能被给定整数整除。关键在于将k+1的情形转化为k的情形，通常通过加上除数的倍数来实现。

Example: Prove that 7ⁿ – 1 is divisible by 6 for all positive integers n.

示例：证明7ⁿ – 1对所有正整数n都能被6整除。

Base Case: n = 1: 7¹ – 1 = 6, which is divisible by 6.

基础情形：n = 1时：7¹ – 1 = 6，能被6整除。

Inductive Hypothesis: Assume 7ᵏ – 1 = 6m for some integer m.

归纳假设：假设7ᵏ – 1 = 6m，其中m为某个整数。

Inductive Step: Consider 7ᵏ⁺¹ – 1 = 7·7ᵏ – 1. Rewrite as 7(7ᵏ – 1) + 6 = 7(6m) + 6 = 6(7m + 1), which is divisible by 6.

归纳步骤：考虑7ᵏ⁺¹ – 1 = 7·7ᵏ – 1。改写为7(7ᵏ – 1) + 6 = 7(6m) + 6 = 6(7m + 1)，能被6整除。

Therefore, by induction, 7ⁿ – 1 is divisible by 6 for all n ≥ 1.

因此，由归纳法可知，7ⁿ – 1对所有n ≥ 1都能被6整除。

5. Induction and Inequalities | 归纳法与不等式

Induction is also effective for proving inequalities, especially those involving powers or factorials. A common technique is to use the inductive hypothesis and then strengthen or manipulate the inequality.

归纳法也适用于证明不等式，尤其是涉及幂或阶乘的不等式。常用技巧是利用归纳假设，然后加强或操作不等式。

Example: Prove that for all n ≥ 5, 2ⁿ > n².

示例：证明对所有n ≥ 5，有2ⁿ > n²。

Base Case: n = 5: 2⁵ = 32 > 25 = 5², true.

基础情形：n = 5时：2⁵ = 32 > 25 = 5²，成立。

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

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

Inductive Step: We need to show 2ᵏ⁺¹ > (k+1)². Since 2ᵏ⁺¹ = 2·2ᵏ > 2k², it suffices to prove 2k² > (k+1)² = k² + 2k + 1, which is equivalent to k² – 2k – 1 > 0. For k ≥ 5, k² – 2k – 1 = (k-1)² – 2 > 14 > 0. Therefore 2ᵏ⁺¹ > 2k² > (k+1)².

归纳步骤：我们需要证明2ᵏ⁺¹ > (k+1)²。由于2ᵏ⁺¹ = 2·2ᵏ > 2k²，只需证明2k² > (k+1)² = k² + 2k + 1，即k² – 2k – 1 > 0。当k ≥ 5时，k² – 2k – 1 = (k-1)² – 2 > 14 > 0。因此2ᵏ⁺¹ > 2k² > (k+1)²。

Thus the inequality holds by induction.

因此该不等式由归纳法得证。

6. Strong Induction (Second Principle) | 强归纳法（第二原理）

Sometimes the statement P(k+1) cannot be proved directly from P(k), but can be proved from P(j) for some j ≤ k. In such cases we use strong induction, where the inductive hypothesis assumes that P(1), P(2), …, P(k) are all true.

有时P(k+1)无法直接从P(k)推出，但可以从某个j ≤ k的P(j)推出。此时我们使用强归纳法，其归纳假设是P(1), P(2), …, P(k)全都成立。

Strong Induction Steps:

强归纳法步骤：

Base case: Verify P(1) (and sometimes P(2) if needed).
Inductive hypothesis: Assume P(1), P(2), …, P(k) are all true for some k.
Inductive step: Use any of these assumptions to prove P(k+1).

基础情形：验证P(1)成立（若需要也验证P(2)）。
归纳假设：假设P(1), P(2), …, P(k)对某个k均成立。
归纳步骤：利用这些假设中的任意一个来证明P(k+1)。

Strong induction is particularly useful for sequences defined recursively, where the k-th term depends on earlier terms, not just the immediate previous term.

强归纳法特别适用于递归定义的数列，其中第k项依赖于更早的项，而不只是前一项。

7. Inductive Proofs with Recurrence Relations | 递归数列的归纳证明

When a sequence is defined by a recurrence relation, induction is often the natural way to prove a closed-form formula or a property of the sequence. The inductive step becomes an algebraic substitution.

当数列由递推关系定义时，归纳法通常是证明通项公式或性质的自然方法。归纳步骤变为代数代入。

Example: Let a₁ = 2 and aₙ₊₁ = 3aₙ + 1 for n ≥ 1. Prove that aₙ = 3ⁿ – 1 for all n ≥ 1.

示例：设a₁ = 2，且对n ≥ 1有aₙ₊₁ = 3aₙ + 1。证明对一切n ≥ 1，有aₙ = 3ⁿ – 1。

Base Case: n = 1: a₁ = 2 = 3¹ – 1, true.

基础情形：n = 1时：a₁ = 2 = 3¹ – 1，成立。

Inductive Hypothesis: Assume aₖ = 3ᵏ – 1.

归纳假设：假设aₖ = 3ᵏ – 1。

Inductive Step: aₖ₊₁ = 3aₖ + 1 = 3(3ᵏ – 1) + 1 = 3ᵏ⁺¹ – 3 + 1 = 3ᵏ⁺¹ – 2? Wait, this gives 3ᵏ⁺¹ – 2, which is not 3ᵏ⁺¹ – 1. Let’s check the recurrence again.

归纳步骤：aₖ₊₁ = 3aₖ + 1 = 3(3ᵏ – 1) + 1 = 3ᵏ⁺¹ – 3 + 1 = 3ᵏ⁺¹ – 2？等一下，这给出3ᵏ⁺¹ – 2，而不是3ᵏ⁺¹ – 1。让我们再检查递推关系。

Indeed, if a₁ = 2 and aₙ₊₁ = 3aₙ + 1, then a₂ = 3·2 + 1 = 7, but 3² – 1 = 8, so the claimed formula is false. Let us correct the example to aₙ = (3ⁿ + 1)/2 instead.

确实，若a₁ = 2且aₙ₊₁ = 3aₙ + 1，则a₂ = 3·2 + 1 = 7，而3² – 1 = 8，所以所给通项公式不成立。让我们将示例更正为aₙ = (3ⁿ + 1)/2。

Correct example: Let a₁ = 2 and aₙ₊₁ = 3aₙ – 1. Then prove aₙ = (3ⁿ + 1)/2.

更正后的示例：设a₁ = 2，且aₙ₊₁ = 3aₙ – 1。证明aₙ = (3ⁿ + 1)/2。

Base Case: n = 1: (3¹ + 1)/2 = 2, true.

基础情形：n = 1时：(3¹ + 1)/2 = 2，成立。

Inductive Step: aₖ₊₁ = 3aₖ – 1 = 3·(3ᵏ + 1)/2 – 1 = (3ᵏ⁺¹ + 3)/2 – 1 = (3ᵏ⁺¹ + 1)/2, which matches the formula for k+1.

归纳步骤：aₖ₊₁ = 3aₖ – 1 = 3·(3ᵏ + 1)/2 – 1 = (3ᵏ⁺¹ + 3)/2 – 1 = (3ᵏ⁺¹ + 1)/2，与k+1的公式相符。

Therefore the closed form is proved.

因此通项公式得证。

8. Common Mistakes and Pitfalls | 常见错误与陷阱

Many students lose marks in induction proofs by making avoidable errors. Being aware of these pitfalls is crucial.

许多学生因可避免的错误在归纳证明中失分。意识到这些陷阱至关重要。

Mistake \| 错误	Consequence \| 后果
Skipping the base case	The chain of reasoning has no starting point.
Assuming P(k) is true without clearly stating it	The proof is incomplete; the hypothesis must be explicit.
Using the statement P(k+1) that you are trying to prove	This is circular reasoning.
Algebra errors when manipulating expressions	Invalid proof even if the idea is correct.

错误	后果
跳过基础情形	推理链没有起点。
未明确写出归纳假设就假设P(k)成立	证明不完整；必须明确写出假设。
使用待证明的P(k+1)本身	这是循环论证。
代数化简错误	即使思路正确，证明也无效。

Another common mistake is changing the index variable incorrectly. For example, writing P(k+1) as “1+2+…+k+1” instead of “1+2+…+k+(k+1)” can lead to ambiguity.

另一个常见错误是指标变量使用不当。例如，将P(k+1)写成”1+2+…+k+1″而不是”1+2+…+k+(k+1)”会导致歧义。

9. Why Does Induction Work? The Well-Ordering Principle | 归纳法为什么有效？良序原理

Mathematical induction is not merely a technique; it is based on a fundamental property of the natural numbers: the Well-Ordering Principle. This principle states that every non-empty set of positive integers has a least element.

数学归纳法不仅仅是一种技巧；它基于自然数的一个基本性质：良序原理。该原理指出，每个非空的正整数集合都有一个最小元素。

To see why induction is valid, suppose that P(1) is true and that whenever P(k) is true, P(k+1) is true. If P(n) were not true for some n, then the set S of positive integers for which P(n) is false would be non-empty. By the Well-Ordering Principle, S has a smallest element, say m. Since P(1) is true, m cannot be 1. Thus m ≥ 2, so m – 1 is a positive integer. Since m is the smallest counterexample, P(m-1) is true. But then the inductive step implies P(m) is true, a contradiction. Therefore S must be empty, so P(n) is true for all n.

为了理解归纳法的有效性，假设P(1)成立，且只要P(k)成立就有P(k+1)成立。如果P(n)对某个n不成立，那么使P(n)为假的正整数集合S非空。根据良序原理，S有最小元素，记为m。由于P(1)成立，m不能是1。因此m ≥ 2，所以m – 1是正整数。因为m是最小反例，P(m-1)成立。但根据归纳步骤，P(m)也应成立，矛盾。因此S必为空，所以P(n)对所有n成立。

10. Tips for IB Exam Success | IB考试成功要点

Here are some practical tips to help you score full marks on induction questions in IB exams.

以下是一些实用技巧，帮助你在IB考试的归纳法题目中拿满分。

Always start by clearly defining P(n), e.g., “Let P(n) be the statement …”.
Test the base case with exact values and explicitly state that it is true.
Write the inductive hypothesis in full, using the variable k.
In the inductive step, show every algebraic manipulation; do not skip steps.
End the proof with a conclusion sentence: “Therefore, by mathematical induction, P(n) is true for all n ≥ 1.”

一开始就明确定义P(n)，例如”设P(n)为命题……”。
用具体数值验证基础情形，并明确说明其成立。
完整写出归纳假设，使用变量k。
在归纳步骤中，展示每一步代数变换，不要跳步。
以结论句结束证明：”因此，由数学归纳法，P(n)对所有n ≥ 1成立。”

Remember that IB examiners award marks for the structure of the proof, not only for the final answer. A clear, well-structured induction proof will earn full marks.

请记住，IB考官按证明结构给分，而不只看最终答案。清晰、结构良好的归纳证明能获得满分。

Published by TutorHao | Mathematics Revision Series | aleveler.com

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

IB Mathematics: Proof by Mathematical Induction | IB数学：数学归纳法证明技巧