Mathematical Induction | 数学归纳法

📚 Mathematical Induction | 数学归纳法

Mathematical induction is a powerful proof technique used throughout the IB Mathematics: Analysis and Approaches (AA) and Applications and Interpretation (AI) courses. It allows us to establish that a statement involving a natural number n holds for all positive integers. Often compared to falling dominoes, the method relies on proving a base case and then showing that if the statement is true for an arbitrary case, it must be true for the next one. This article provides a comprehensive yet accessible guide to induction, including step-by-step examples on sums, divisibility, inequalities, and sequences, along with common pitfalls and an introduction to strong induction.

数学归纳法是IB数学课程（包括分析与方法和应用与解释）中一种强大的证明工具。它能够帮助我们证明涉及自然数n的命题对所有正整数都成立。这个方法常被比作多米诺骨牌：首先证明第一张牌会倒下（基础情况），然后证明任意一张牌倒下会使下一张牌也倒下（归纳步骤）。本文将系统地讲解归纳法，通过求和、整除性、不等式、数列等实例逐步展示证明过程，同时指出常见错误并简要介绍强归纳法。

---

1. Introduction to Mathematical Induction | 数学归纳法简介

In IB Mathematics, you will often be asked to prove that a formula or property holds for all natural numbers n. Direct verification is impossible because n can be arbitrarily large. Mathematical induction bridges this gap by reducing an infinite verification to two finite steps. The core idea is to prove a statement P(n) for all n by first showing P(1) is true (base case) and then proving that whenever P(k) is true, P(k+1) is also true (inductive step).

在IB数学中，我们经常需要证明某个公式或性质对所有自然数n成立。由于n可以无限大，直接逐一验证是不现实的。数学归纳法通过将无穷验证转化为两个有限步骤解决了这个问题。其核心思想是：证明命题P(n)对所有n成立，只需先验证P(1)为真（基础情况），再证明只要P(k)为真，P(k+1)就一定为真（归纳步骤）。

---

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

Formally, the principle of mathematical induction states: Let P(n) be a statement about a positive integer n. If
(i) P(1) is true, and
(ii) for every integer k ≥ 1, the truth of P(k) implies the truth of P(k+1),
then P(n) is true for all positive integers n.
This principle is an axiom of the natural numbers and underpins many proofs in algebra, number theory, and combinatorics encountered in the IB syllabus.

数学归纳法原理可以严格表述为：设P(n)是一个关于正整数n的命题。如果
(i) P(1)为真，并且
(ii) 对任意整数k ≥ 1，P(k)为真能够推出P(k+1)为真，
那么P(n)对所有正整数n都成立。
这一原理是自然数体系的一条公理，也是IB课程中代数、数论和组合证明的基础。

---

3. The Base Case: Starting the Domino Effect | 基本情况：启动多米诺效应

r depending on the domain. Always read the problem carefully to identify the smallest value of n for which the statement is claimed.

基本情况就像第一张必须推倒的多米诺骨牌。通常我们需要将n = 1代入命题，验证等式两边相等或性质成立。有时基本情况的起始值可能是n = 0、n = 2或其他小整数，这取决于命题的定义域。务必仔细审题，确定命题所宣称的最小n值。

For example, to prove that 2ⁿ > n for all n ≥ 1, we check the base case n = 1: 2¹ h is true. A common mistake is to forget the base case entirely or to assume it is obvious— e whole proof collapses, because there is no starting point for the chain of implications.

例如，要证明对任意n ≥ 1有2ⁿ > n，我们检查n = 1的基本情况：2¹ = 2 > 1，成立。一个常见错误是完全忘记证明基本情况，或认为它显然成立——没有基本情况，整个证明链就失去了起点，证明因此无效。

---

4. The Inductive Hypothesis: Assuming the Statement | 归纳假设：假设命题成立

In the inductive step, we assume that P(k) holds for some arbitrary positive integer k. This is called the inductive hypothesis. The assumption is not that the statement is true for all n, but only for a particular, yet arbitrary, k. Using this hypothesis, we then aim to prove that P(k+1) follows logically. This assumption is legitimate because we are establishing a conditional link: if the statement works for k, it must work for the next number.

在归纳步骤中，我们假设对于某个任意的正整数k，P(k)成立。这个假设称为归纳假设。注意这里并不是假设命题对所有n成立，而仅仅是针对某个特定但又任意的k。我们利用这个假设去证明P(k+1)成立。这种假设是合理的，因为我们正在建立一种条件联系：如果命题对k成立，那么它对下一个自然数也必然成立。

In IB exam solutions, it is standard practice to write 'Assume true for n = k' or 'Assume P(k) is true' learly stating this hypothesis not only structures your proof but also earns method marks.

在IB考试的解答中，习惯上写着“假设当n = k时命题成立”或“假设P(k)为真”。清晰地写下归纳假设不仅能理清证明的结构，还能获得方法分数。

---

5. The Inductive Step: Proving the Implication | 归纳步骤：证明蕴含关系

mula, or using the hypothesis to simplify an expression. The goal is to show that the statement for k+1 takes the same form as the original claim but with n replaced by k+1.

归纳步骤是整个证明的核心。我们从归纳假设P(k)出发，推导出P(k+1)。这通常涉及代数变形，例如在求和式中加上下一项、将n = k+1代入公式，或用归纳假设来化简表达式。我们的目标是证明k+1时的命题形式与原始命题一致，只是将n替换为k+1。

For instance, when proving the sum formula 1 + 2 + … + n = n(n+1)/2, the inductive step requires showing that if 1 + 2 + … + k = k(k+1)/2, then 1 + 2 + … thesis and simplifying. The logic is crisp and reproducible across many types of problems.

例如，在证明求和公式1 + 2 + … + n = n(n+1)/2时，归纳步骤需要证明：若1 + 2 + … + k = k(k+1)/2，则1 + 2 + … + k + (k+1) = (k+1)(k+2)/2。我们将(k+1)加到假设等式的两边并化简，即可完成。这种逻辑清晰明了，适用于多种类型的问题。

---

6. Common Pitfalls and How to Avoid Them | 常见陷阱与避免方法

Students often struggle with the inductive step because they try to prove P(k+1) without using the inductive hypothesis. A valid inductive step must explicitly invoke the assumption P(k). Another pitfall is incorrectly simplifying algebraic expressions, especially when fractions, exponents, or factorials are involved. Always double-check your algebra and ensure the final form matches P(k+1) exactly.

学生在归纳步骤中常犯的错误是试图绕过归纳假设直接证明P(k+1)。一个有效的归纳步骤必须明确地用到假设P(k)。另一个常见陷阱是代数化简出错，特别是涉及分数、指数或阶乘时。务必仔细检查每一步代数运算，并确保最终形式与P(k+1)完全一致。

Additionally, avoid the 'base case only for n=1' missing inductive hypothesis statements cost vital marks despite a correct algebraic flow.

此外，当题目指明n ≥ 2时，不要想当然地只验证n=1。必须严格遵守n的定义域。在IB阅卷中，即使后续代数过程正确，遗漏基本情况或未清晰写出归纳假设都会导致失分。

---

广告 / Sponsored

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

Let us prove the classic formula: 1 + 2 + 3 + … + n = n(n+1)/2 for all n ∈ ℕ.
Base case: n = 1. Left side = 1. Right side = 1×2/2 = 1. True.
Inductive hypothesis: Assume for some k ≥ 1, 1 + 2 + … + k = k(k+1)/2.
Inductive step: Consider the sum up to k+1: 1 + 2 + … /2. This is exactly the formula with n = k+1. Hence the truth for k implies truth for k+1.
Conclusion: By mathematical induction, the formula holds for all positive integers n.

我们来证明经典公式：对所有n ∈ ℕ，1 + 2 + 3 + … + n = n(n+1)/2。
基本情况：n = 1。左边 = 1，右边 = 1×2/2 = 1。成立。
归纳假设：假设对某个k ≥ 1，有1 + 2 + … + k = k(k+1)/2。
归纳步骤：考虑前k+1项和：1 + 2 + … + k + (k+1)。根据假设，它等于k(k+1)/2 + (k+1)。提取公因式(k+1)得：(k+1)(k/2 + 1) = (k+1)(k+2)/2。这恰为n = k+1时的公式。因此k成立推出k+1成立。
结论：由数学归纳法，该公式对所有正整数n成立。

---

8. Example: Proving Divisibility | 示例：证明整除性

Divisibility proofs are common in IB AA. Show that 5ⁿ − 1 is divisible by 4 for all n ∈ ℕ.
Base case: n = 1: 5¹ − 1 = 4, divisible by 4.
Inductive hypothesis: Assume 5^k − 1 = 4m for some integer m.
Inductive step: We need to prove 5^k+1 − 1 is divisible by 4. Write 5^k+1 − 1 = 5·5^k − 1 = 5(5^k − 1) + 4. Using the hypothesis, 5^k ly a multiple of 4. Thus P(k+1) holds. This elegant manipulation is a typical IB question.

整除性证明在IB AA中很常见。证明对所有自然数n，5ⁿ − 1可被4整除。
基本情况：n = 1：5¹ − 1 = 4，能被4整除。
归纳假设：假设对某个整数m，5^k − 1 = 4m。
归纳步骤：需证5^k+1 − 1能被4整除。将其写作5^k+1 − 1 = 5·5^k − 1 = 5(5^k − 1) + 4。利用假设5^k − 1 = 4m，表达式变为5·4m + 4 = 4(5m + 1)，显然是4的倍数。因此P(k+1)成立。这种巧妙的变形是IB考试中的典型题。

---

9. Example: Proving Inequalities | 示例：证明不等式

Prove by induction that 2ⁿ > n² for all integers n ≥ 5. (Note the adjusted base case.)
Base case: n = 5: 2⁵ = 32, 5² = 25, 32 > 25, true.
Inductive hypothesis: Assume 2^k > k² for some k ≥ 5.
Inductive step: Show 2^k+1 > (k+1)². Start with 2^k+1 = 2·2^k > 2·k² (by hypothesis). We need 2k² ≥ (k+1)² for k ≥ 5. Expand (k+1)² = k² + 2k + 1. Then 2k² − (k² + 2k + 1) = k² − 2k − 1 = (k−1)² − 2. For k ≥ 5, (k−1)² ≥ 16, so this difference is positive. Hence 2k² > (k+1)², and the inequality holds. This type of reasoning often requires an additional sub-proof or comparison of growth rates, a valuable skill in IB HL.

用归纳法证明对所有整数n ≥ 5，有2ⁿ > n²。（注意基本情况的调整。）
基本情况：n = 5：2⁵ = 32，5² = 25，32 > 25，成立。
归纳假设：假设对某个k ≥ 5，2^k > k²。
归纳步骤：证明2^k+1 > (k+1)²。从2^k+1 = 2·2^k > 2·k²（根据假设）出发。我们需要证明当k ≥ 5时2k² ≥ (k+1)²。展开(k+1)² = k² + 2k + 1。则2k² − (k² + 2k + 1) = k² − 2k − 1 = (k−1)² − 2。当k ≥ 5时，(k−1)² ≥ 16，因此该差值为正。故2k² > (k+1)²，不等式成立。这类推理往往需要额外的子证明或增长率比较，是IB HL中宝贵的能力。

---

10. Example: Sequences and Recurrence Relations | 示例：数列与递推关系

Induction is also used to verify closed forms of sequences defined recursively. Consider the recurrence u_n+1 = 3u_n − 2 with u₁ = 2. Prove that u_n = 3ⁿ⁻¹ + 1 for n ≥ 1.
Base case: n = 1: u₁ = 2, formula gives 3⁰ + 1 = 2. True.
Inductive hypothesis: Assume u_k = 3^k−1 + 1.
Inductive step: For k+1, use the recurrence: u_k+1 = 3u_k − 2 = 3(3^k−1 + 1) − 2 = 3^k + 3 − 2 = 3^k + 1. This matches the formula when n = k+1 (3^(k+1)−1 + 1 = 3^k + 1). Thus the closed form is proven. Such questions integrate sequence knowledge with proof technique.

归纳法还常用于验证递推数列的通项公式。考虑递推关系u_n+1 = 3u_n − 2且u₁ = 2。证明u_n = 3ⁿ⁻¹ + 1对所有n ≥ 1成立。
基本情况：n = 1：u₁ = 2，公式给出3⁰ + 1 = 2。成立。
归纳假设：假设u_k = 3^k−1 + 1。
归纳步骤：对于k+1，利用递推关系：u_k+1 = 3u_k − 2 = 3(3^k−1 + 1) − 2 = 3^k + 3 − 2 = 3^k + 1。这与n = k+1时的公式吻合（3^(k+1)−1 + 1 = 3^k + 1）。通项公式得证。这类题目将数列知识与证明技巧融为一体。

---

11. Strong Induction: An Extension | 强归纳法：一种扩展

Sometimes the truth of P(k+1) depends on more than just P(k); it may require P(1), P(2), … duction appears in IB with problems like proving that every integer greater than 1 can be written as a product of primes, or in certain sequence and tiling problems.

有时P(k+1)的成立不仅依赖于P(k)，还可能需要P(1)、P(2)、…、P(k)全部为真。强归纳法假设命题对所有不超过k的值都成立。其步骤为：(i) 根据所需验证基本情况，(ii) 假设对所有j ≤ k，P(j)为真，(iii) 证明P(k+1)。在IB中，强归纳法可见于诸如证明每个大于1的整数都可以写成素数乘积的问题，或某些数列与铺砖问题。

---

12. Summary: Why Induction Matters in IB Mathematics | 总结：为什么归纳法在IB数学中重要

Mathematical induction is more than an exam topic; it develops logical reasoning, algebraic fluency, and the ability to construct rigorous arguments. In IB AA, induction is explicitly examined, often in Paper 1 and Paper 2, while in AI it supports a deeper understanding of patterns and models. Mastering induction teaches you to handle infinite certainty with finite steps—an essential skill for further mathematics, computer science, and scientific reasoning.

数学归纳法不仅是一个考试主题，它还培养逻辑推理、代数流畅性以及构建严密论证的能力。在IB AA中，归纳法是明确的考查内容，常出现在试卷一和试卷二；在AI中，它有助于更深入地理解规律和模型。掌握归纳法意味着学会用有限步骤获取无限确定性，这是高等数学、计算机科学和科学推理中不可或缺的素养。

Published by TutorHao | IB Mathematics Revision Series | aleveler.com

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