IB Mathematics AA: Proof by Induction and Divisibility — IB数学AA：数学归纳法与整除性证明

Introduction to Mathematical Induction — 数学归纳法入门

Mathematical induction is one of the most powerful and elegant proof techniques in mathematics. It is a cornerstone of the IB Mathematics: Analysis and Approaches (AA) syllabus, appearing in both Standard Level and Higher Level examinations. At its core, induction allows us to prove that a statement P(n) holds true for all natural numbers n >= k, where k is some starting integer — typically 0 or 1. Unlike deductive reasoning, which moves from general principles to specific conclusions, induction works in the opposite direction: we establish a base case, then show that if the statement holds for some arbitrary integer, it must also hold for the next one. This “domino effect” is what gives induction its unique power and beauty.

数学归纳法是数学中最强大、最优雅的证明技巧之一。它是 IB 数学：分析与方法（AA）课程的核心内容，出现在标准级别和高级级别的考试中。归纳法的核心在于，它使我们能够证明一个命题 P(n) 对于所有自然数 n >= k 都成立，其中 k 是某个起始整数，通常是 0 或 1。与从一般原则推导出具体结论的演绎推理不同，归纳法的运作方向恰恰相反：我们首先建立基础情形，然后证明如果命题对于某个任意整数成立，那么它对于下一个整数也必然成立。这种”多米诺骨牌效应”赋予了归纳法独特的威力和美感。

The Two-Step Framework of Induction — 归纳法的两步框架

Every proof by induction follows a strict two-step structure, and IB examiners are meticulous about awarding marks only when both steps are clearly presented. Here is the canonical format you must master:

每一个归纳法证明都严格遵循两步结构，而 IB 阅卷人对这两步是否清晰呈现要求极为严格。以下是你必须掌握的标准格式：

Step 1: The Base Case — 第一步：基础情形

Prove that P(k) is true for the smallest allowable value of n. This is typically n = 1 or n = 0, but the question may specify a different starting point. The base case is non-negotiable; without it, the entire proof collapses. Think of it as placing the first domino upright — if it falls, nothing follows.

证明 P(k) 对于 n 的最小允许取值成立。通常是 n = 1 或 n = 0，但题目可能指定不同的起点。基础情形是不可省略的；没有它，整个证明就会崩溃。可以把它想象成竖起第一张多米诺骨牌 — 如果它倒不下去，后面就什么都发生不了。

Step 2: The Inductive Step — 第二步：归纳步骤

Assume P(m) is true for some arbitrary integer m >= k. This assumption is called the inductive hypothesis. Using this hypothesis, you must then prove that P(m + 1) is also true. This is the “push” that knocks over the next domino. Once both steps are established, you conclude by the principle of mathematical induction that P(n) is true for all n >= k.

假设 P(m) 对于某个任意整数 m >= k 成立。这一假设被称为归纳假设。利用这个假设，你必须接着证明 P(m + 1) 也成立。这就是推倒下一张多米诺骨牌的”推力”。一旦两步都建立，你就可以根据数学归纳法原理得出结论：P(n) 对于所有 n >= k 成立。

Divisibility Proofs: The Classic IB Induction Problem — 整除性证明：经典 IB 归纳法问题

One of the most frequently tested applications of induction in IB Mathematics AA is proving divisibility statements. A typical question might read: “Prove by induction that 7^n – 1 is divisible by 6 for all n in N.” These problems follow a predictable pattern, and once you master the algebraic manipulation required in the inductive step, they become remarkably straightforward.

在 IB 数学 AA 中，最常考的归纳法应用之一就是证明整除性命题。典型的题目可能是这样的：”用归纳法证明 7^n – 1 对所有自然数 n 都能被 6 整除。”这类问题遵循可预测的模式，一旦你掌握了归纳步骤中所需的代数操作，它们就变得异常简单。

The key insight in divisibility proofs is that the inductive hypothesis gives you an expression that is divisible by some number d, and you must rearrange P(m + 1) to extract that expression. Here is a worked example:

整除性证明的关键洞见在于：归纳假设给了你一个能被某个数 d 整除的表达式，而你必须重新排列 P(m + 1) 来提取出那个表达式。以下是一个详细示例：

Common Divisibility Patterns in IB Exams — IB 考试中的常见整除模式

IB examiners favour certain algebraic forms when setting induction questions on divisibility. Recognising these patterns can save you valuable time in the exam. Here are the three most common templates:

IB 出题人在设置归纳法整除性问题时偏爱某些代数形式。识别这些模式可以在考试中为你节省宝贵的时间。以下是最常见的三种模板：

1. a^n – b^n is divisible by (a – b) — This is a direct consequence of the factorisation formula. Induction can prove this, but recognising the factorisation is often faster. Example: 5^n – 3^n is divisible by 2 for all n in N.

1. a^n – b^n 能被 (a – b) 整除 — 这是因式分解公式的直接结果。归纳法可以证明这一点，但识别因式分解通常更快。例题：对于所有自然数 n，5^n – 3^n 能被 2 整除。

2. a^n + b^n is divisible by (a + b) when n is odd — This is a subtle but important variant. For odd n, a^n + b^n factorises with (a + b) as a factor. Example: 4^n + 6^n is divisible by 10 for all odd n.

2. 当 n 为奇数时，a^n + b^n 能被 (a + b) 整除 — 这是一个微妙但重要的变体。对于奇数 n，a^n + b^n 可以因式分解出 (a + b)。例题：对于所有奇数 n，4^n + 6^n 能被 10 整除。

3. Expressions of the form a x b^n + c — These require clever algebraic manipulation in the inductive step. You typically need to add and subtract strategically, or factor out a common term. Example: 3^(2n) – 2^n is divisible by 7 for all n in N.

3. 形如 a x b^n + c 的表达式 — 这些需要在归纳步骤中进行巧妙的代数操作。你通常需要有策略地加减某一项，或提取公因子。例题：对于所有自然数 n，3^(2n) – 2^n 能被 7 整除。

Worked Example: A Classic IB Question — IB 真题示例

Let us work through a more challenging IB-style question that combines induction with the algebraic manipulation skills typical of the HL paper.

让我们来完成一道更具挑战性的 IB 风格题目，这道题将归纳法与 HL 试卷中典型的代数操作技巧结合在一起。

Solution — 解答

Base Case (n = 1):
5^(2×1) – 1 = 5^2 – 1 = 25 – 1 = 24, which is divisible by 24. Done.

基础情形 (n = 1)：
5^(2×1) – 1 = 5^2 – 1 = 25 – 1 = 24，能被 24 整除。Done.

Inductive Hypothesis: Assume that 5^(2m) – 1 = 24k for some integer k. Equivalently, 5^(2m) = 24k + 1.

归纳假设：假设 5^(2m) – 1 = 24k，其中 k 为某整数。即 5^(2m) = 24k + 1。

Inductive Step (prove for n = m + 1):
5^(2(m+1)) – 1 = 5^(2m+2) – 1
= 5^2 x 5^(2m) – 1
= 25 x 5^(2m) – 1
= 25(24k + 1) – 1    (substituting the inductive hypothesis)
= 600k + 25 – 1
= 600k + 24
= 24(25k + 1)

归纳步骤（证明 n = m + 1 的情况）：
5^(2(m+1)) – 1 = 5^(2m+2) – 1
= 5^2 x 5^(2m) – 1
= 25 x 5^(2m) – 1
= 25(24k + 1) – 1    （代入归纳假设）
= 600k + 25 – 1
= 600k + 24
= 24(25k + 1)

Since 25k + 1 is an integer, the expression is divisible by 24. Therefore, by the principle of mathematical induction, 5^(2n) – 1 is divisible by 24 for all integers n >= 1. QED

由于 25k + 1 是整数，该表达式能被 24 整除。因此，根据数学归纳法原理，5^(2n) – 1 对所有整数 n >= 1 都能被 24 整除。QED

Induction for Inequalities — 不等式的归纳法证明

While divisibility is the most common induction topic in IB, inequalities also appear regularly. Proving statements like 2^n > n^2 for n >= 5 requires a slightly different approach. The key is to use the inductive hypothesis to construct a chain of inequalities that leads to the desired result.

虽然整除性是 IB 考试中最常见的归纳法主题，不等式也会经常出现。证明像”当 n >= 5 时，2^n > n^2″这样的命题需要稍有不同的方法。关键是要利用归纳假设构建一个不等式链条，最终推导出所需的结果。

For example, to prove 2^n > n for all n >= 1:

例如，证明 2^n > n 对所有 n >= 1 成立：

Notice that the inequality direction must be carefully preserved, and you often need to justify each transition — for instance, showing that 2m >= m + 1 for m >= 1. IB marks are awarded for these justifications, not just the algebraic manipulation alone.

请注意，不等号方向必须仔细保持，并且你通常需要为每次转换提供理由 — 例如，证明对于 m >= 1，有 2m >= m + 1。IB 会为这些理由而非仅仅代数操作而给分。

Strong Induction: A Powerful Extension — 强归纳法：一个强大的扩展

IB Higher Level students should also be aware of strong induction, a variant where instead of assuming only P(m) to prove P(m+1), you assume P(k), P(k+1), …, P(m) all hold. This is particularly useful for problems involving recurrence relations or sequences where each term depends on more than one previous term. For example, proving that every integer n >= 2 can be expressed as a product of prime numbers is a classic application of strong induction.

IB 高级别的学生还应了解强归纳法，这是一种变体，在其中你不是只假设 P(m) 成立来证明 P(m+1)，而是假设 P(k), P(k+1), …, P(m) 全部成立。这在使用递推关系或序列（其中每一项都依赖于多个前项）的问题中特别有用。例如，证明每个整数 n >= 2 都可以表示为质数的乘积，就是强归纳法的一个经典应用。

Common Pitfalls and Exam Tips — 常见陷阱与考试技巧

After marking thousands of IB induction proofs, certain errors recur with alarming frequency. Here is what to watch out for:

在批改了数千份 IB 归纳法证明之后，某些错误以惊人的频率反复出现。以下是需要注意的事项：

1. Forgetting the Conclusion: Many students complete the base case and inductive step, then stop. IB requires an explicit concluding statement: “Therefore, by the principle of mathematical induction, P(n) is true for all integers n >= k.” This is worth a mark — do not throw it away.

1. 忘记结论：许多学生完成了基础情形和归纳步骤后就停笔了。IB 要求一个明确的总结陈述。这一分值得拿 — 不要丢掉它。

2. Circular Reasoning: Using P(m + 1) to prove P(m + 1) is the cardinal sin of induction proofs. You must derive P(m + 1) from P(m), not assume what you are trying to prove. Always ask yourself: am I genuinely using the inductive hypothesis, or am I just rewriting the statement?

2. 循环论证：用 P(m + 1) 来证明 P(m + 1) 是归纳法证明中最大的忌讳。你必须从 P(m) 推导出 P(m + 1)，而不是假设你正要证明的东西。始终问自己：我是否真正使用了归纳假设，还是我只是在重写命题？

3. Incorrect Base Case: If the question asks you to prove something for n >= 3, do not use n = 1 as your base case. The base case must match the domain specified in the statement.

3. 基础情形错误：如果题目要求你证明某命题对于 n >= 3 成立，不要使用 n = 1 作为基础情形。基础情形必须与命题中指定的定义域匹配。

4. Algebraic Sloppiness in Divisibility Proofs: The “add and subtract” trick (adding and subtracting the same term to create a recognisable factor) is the heart of divisibility induction. Practise it extensively — it accounts for roughly 60% of errors in student work. Drill the techniques of rewriting a^(m+1) in terms of a^m, and adding/subtracting constants to reveal the inductive hypothesis.

4. 整除性证明中的代数草率：“加减同一项”的技巧（添加和减去相同的项来产生可识别的因子）是整除性归纳法的核心。大量练习这一点 — 它在学生作业中大约占了 60% 的错误来源。反复训练将 a^(m+1) 用 a^m 重写的技巧，以及加减常数以揭示归纳假设的方法。

Summary and Key Takeaways — 总结与关键要点

Mathematical induction is not merely a topic to memorise for the IB examination — it is a mode of reasoning that appears throughout higher mathematics, from number theory to graph theory, from combinatorics to computer science. Mastering induction means mastering a way of thinking: if it works for the first case, and each case implies the next, then it works for all cases.

数学归纳法不仅仅是 IB 考试中需要记忆的一个知识点 — 它是一种推理方式，贯穿于高等数学的各个领域，从数论到图论，从组合数学到计算机科学。掌握归纳法意味着掌握一种思维方式：如果它对第一种情况成立，且每种情况都蕴含着下一种情况，那么它对所有情况都成立。

For IB Mathematics AA students, the pathway to success is clear: practise the two-step structure until it becomes second nature, drill the algebraic manipulations required for divisibility proofs, and always — always — write the concluding statement. With disciplined practice, induction transforms from a source of anxiety into one of the most reliable marks on the paper.

对于 IB 数学 AA 的学生来说，通往成功的路径是清晰的：反复练习两步结构直到它成为第二天性；大量训练整除性证明所需的代数操作；并且永远、永远要写出总结陈述。通过有纪律的练习，归纳法将从焦虑的来源转变为试卷上最可靠的得分点之一。