Proof by Induction | 数学归纳法

📚 Proof by Induction | 数学归纳法

Proof by induction is one of the most elegant and powerful tools in the A-Level Edexcel Mathematics syllabus. It allows you to prove statements involving positive integers, such as summation formulas, divisibility results, and properties of sequences. In this article, we will walk through the core ideas, step-by-step methods, and multiple worked examples to help you master this topic.

数学归纳法是 A-Level Edexcel 数学大纲中最优雅、最强有力的工具之一。它使你能够证明涉及正整数的命题，例如求和公式、整除性质以及数列的特性。本文将沿着核心思想、分步方法和多个完整例题带你彻底掌握这一主题。

---

1. What Is Mathematical Induction? | 什么是数学归纳法？

Mathematical induction is a method for proving that a statement P(n) is true for every natural number n, where n typically starts from 1, 0, or some other integer. It is not a way of discovering new formulas but a rigorous verification method.

数学归纳法是一种用于证明命题 P(n) 对每个自然数 n 都成立的方法，其中 n 通常从 1、0 或其他某个整数开始。它并非发现新公式的途径，而是一种严格的验证方法。

In Edexcel exams, you are expected to know the structure of an induction proof and apply it to series sums, divisibility, and sequence recurrences.

在 Edexcel 考试中，你应当掌握归纳证明的结构，并将其应用于级数求和、整除性和数列递推关系。

---

2. The Domino Analogy | 多米诺骨牌类比

Think of induction as knocking over an infinite row of dominoes. The base case ensures the first domino falls. The inductive step says: if one domino falls, the next one must fall. Together, they guarantee that all dominoes will fall.

你可以把归纳法想象成推倒一列无限长的多米诺骨牌。基础情形确保第一张骨牌倒下。归纳步骤表明：如果某一张骨牌倒下，下一张也必定倒下。两者结合就保证了所有骨牌都会倒下。

This analogy helps many students visualise why proving P(k) ⇒ P(k+1) is sufficient once the base case is established.

这个类比帮助很多学生直观理解为什么一旦建立起基础情形，证明 P(k) ⇒ P(k+1) 就足够了。

---

3. The Four Standard Steps | 四个标准步骤

Every proof by induction in Edexcel Mathematics follows a clear four-step structure:

在 Edexcel 数学中，每一个归纳证明都遵循清晰的四步结构：

• Step 1 – Base case: Verify P(1) (or the smallest value) is true.
• 第一步 – 基础情形：验证 P(1)（或最小的值）为真。
• Step 2 – Inductive hypothesis: Assume P(k) is true for some integer k ≥ 1.
• 第二步 – 归纳假设：假设对于某个整数 k ≥ 1，P(k) 为真。
• Step 3 – Inductive step: Use the assumption to prove that P(k+1) is true.
• 第三步 – 归纳递推：利用假设证明 P(k+1) 也为真。
• Step 4 – Conclusion: Since base case holds and the implication is true, by induction P(n) is true for all n.
• 第四步 – 结论：因为基础情形成立且蕴含关系为真，由归纳法可知 P(n) 对所有 n 成立。

Examiners allocate marks specifically for each of these parts, so never skip the conclusion statement.

考官会对这几个部分分别给分，因此绝不要省略结论语句。

---

4. Step 1: Base Case – Setting the Foundation | 第一步：基础情形 – 奠定基础

titute 1 into the statement and show that the left-hand side equals the right-hand side or that the property holds.

基础情形通常是 n = 1。你将 1 代入命题，证明左边等于右边，或者该性质成立。

to prove 1 + 2 + ... + n = ½n(n+1), check n=1: LHS = 1, RHS = ½×1×2 = 1. So P(1) is true.

例如，要证明 1 + 2 + ... + n = ½n(n+1)，验证 n=1：左边 = 1，右边 = ½×1×2 = 1。因此 P(1) 为真。

---

5. Step 2: Inductive Hypothesis – The Assumption | 第二步：归纳假设 – 作出假设

You write: "Assume that P(k) is true for some positive integer k." This is the inductive hypothesis and is the key to linking one case to the next.

你写下："假设对于某个正整数 k，P(k) 为真。" 这就是归纳假设，也是连接前后情形的关键。

You must state this clearly. For a sum formula, it means assuming the sum up to k equals a given expression.

你必须清楚地陈述这一点。对于求和公式，这意味着假定前 k 项的和等于某个给定的表达式。

---

6. Step 3: Inductive Step – Proving P(k+1) | 第三步：归纳递推 – 证明 P(k+1)

This is the heart of the proof. You start with the expression for P(k+1) and manipulate it using the assumption P(k) to arrive at the required form.

这是证明的核心。你从 P(k+1) 的表达式出发，利用 P(k) 的假设对其进行整理，最终得到所需的形式。

For sums, this usually means adding the (k+1)th term to both sides of the assumed equality. For divisibility, you factor expressions to reveal the inductive hypothesis.

对于求和，这通常意味着将第 (k+1) 项加到假定等式的两边。对于整除，你需要对表达式进行因式分解以显出归纳假设。

---

7. Step 4: Conclusion – Sealing the Proof | 第四步：结论 – 完成证明

Once you have shown P(k) ⇒ P(k+1), you conclude: "Since P(1) is true and P(k) implies P(k+1), by mathematical induction P(n) is true for all positive integers n."

一旦你证明了 P(k) ⇒ P(k+1)，就可以总结："因为 P(1) 为真且 P(k) 蕴含 P(k+1)，根据数学归纳法，P(n) 对所有正整数 n 成立。"

Some Edexcel mark schemes require the exact phrasing "by the principle of mathematical induction". Check past papers to match their style.

某些 Edexcel 评分标准要求完整说出"根据数学归纳法原理"。查阅往年试题以符合其风格。

---

广告 / Sponsored

8. Example 1: Proving a Summation Formula | 例1：证明求和公式

Prove that for all positive integers n:
1² + 2² + 3² + ... + n² = (1/6)n(n+1)(2n+1).

证明对所有正整数 n 有：
1² + 2² + 3² + ... + n² = (1/6)n(n+1)(2n+1)。

Base case n=1: LHS = 1² = 1, RHS = (1/6)×1×2×3 = 1. True.

基础情形 n=1：左边 = 1² = 1，右边 = (1/6)×1×2×3 = 1。成立。

Inductive hypothesis: Assume for some k: Σ_r=1^k r² = (1/6)k(k+1)(2k+1).

归纳假设：假设对于某个 k：Σ_r=1^k r² = (1/6)k(k+1)(2k+1)。

Inductive step: Consider sum to k+1.
Σ_r=1^k+1 r² = Σ_r=1^k r² + (k+1)²
= (1/6)k(k+1)(2k+1) + (k+1)²
= (k+1)[ (1/6)k(2k+1) + (k+1) ]
= (k+1)[ (2k² + k)/6 + (6k+6)/6 ]
= (k+1)[ (2k² + 7k + 6)/6 ]
= (1/6)(k+1)(k+2)(2k+3).
This is exactly the RHS with n=k+1. So P(k+1) holds.

归纳递推：考虑前 k+1 项的和。
Σ_r=1^k+1 r² = Σ_r=1^k r² + (k+1)²
= (1/6)k(k+1)(2k+1) + (k+1)²
= (k+1)[ (1/6)k(2k+1) + (k+1) ]
= (k+1)[ (2k² + k)/6 + (6k+6)/6 ]
= (k+1)[ (2k² + 7k + 6)/6 ]
= (1/6)(k+1)(k+2)(2k+3)。
这恰好是 n=k+1 时的右边。因此 P(k+1) 成立。

Conclusion: By mathematical induction, the formula is true for all n ∈ ℕ.

结论：根据数学归纳法，该公式对所有自然数 n 成立。

---

9. Example 2: Proving Divisibility | 例2：证明整除性

Prove that 11ⁿ − 4ⁿ is divisible by 7 for all positive integers n.

证明对所有正整数 n，11ⁿ − 4ⁿ 能被 7 整除。

Base case n=1: 11¹ − 4¹ = 7, which is divisible by 7. True.

基础情形 n=1：11¹ − 4¹ = 7，能被 7 整除。成立。

Inductive hypothesis: Assume 11ᵏ − 4ᵏ = 7m for some integer m.

归纳假设：假设 11ᵏ − 4ᵏ = 7m，其中 m 为整数。

Inductive step: For n = k+1,
11^k+1 − 4^k+1 = 11·11ᵏ − 4·4ᵏ
= (7+4)·11ᵏ − 4·4ᵏ
= 7·11ᵏ + 4·11ᵏ − 4·4ᵏ
= 7·11ᵏ + 4(11ᵏ − 4ᵏ)
= 7·11ᵏ + 4(7m) [by inductive hypothesis]
= 7(11ᵏ + 4m).
Since 11ᵏ + 4m is an integer, the expression is a multiple of 7. Hence P(k+1) holds.

归纳递推：考虑 n = k+1，
11^k+1 − 4^k+1 = 11·11ᵏ − 4·4ᵏ
= (7+4)·11ᵏ − 4·4ᵏ
= 7·11ᵏ + 4·11ᵏ − 4·4ᵏ
= 7·11ᵏ + 4(11ᵏ − 4ᵏ)
= 7·11ᵏ + 4(7m) [根据归纳假设]
= 7(11ᵏ + 4m)。
因为 11ᵏ + 4m 是整数，所以该表达式是 7 的倍数。故 P(k+1) 成立。

Conclusion: By induction, 11ⁿ − 4ⁿ is divisible by 7 for all positive integers n.

结论：由归纳法，11ⁿ − 4ⁿ 对所有正整数 n 能被 7 整除。

---

10. Example 3: Recurrence Relation | 例3：递推关系

A sequence is defined by u₁ = 3 and u_n+1 = 2u_n − 1. Prove by induction that u_n = 2ⁿ + 1.

数列由 u₁ = 3 和 u_n+1 = 2u_n − 1 定义。用归纳法证明 u_n = 2ⁿ + 1。

Base case n=1: u₁ = 3, and formula gives 2¹ + 1 = 3. True.

基础情形 n=1：u₁ = 3，公式给出 2¹ + 1 = 3。成立。

Inductive hypothesis: Assume u_k = 2ᵏ + 1 for some k.

归纳假设：假设对某个 k，u_k = 2ᵏ + 1。

Inductive step: Using the recurrence, u_k+1 = 2u_k − 1 = 2(2ᵏ + 1) − 1 = 2·2ᵏ + 2 − 1 = 2^k+1 + 1. This matches the formula for n=k+1. So P(k+1) is true.

归纳递推：利用递推式，u_k+1 = 2u_k − 1 = 2(2ᵏ + 1) − 1 = 2·2ᵏ + 2 − 1 = 2^k+1 + 1。这与 n=k+1 时的公式一致。故 P(k+1) 为真。

Conclusion: By induction, u_n = 2ⁿ + 1 for all n ∈ ℕ.

结论：由归纳法，对所有自然数 n 有 u_n = 2ⁿ + 1。

---

11. Common Mistakes and How to Avoid Them | 常见错误及如何避免

Mistake 1: Forgetting to write the conclusion. Even if the induction step is perfect, you can lose marks. Always finish with a clear concluding sentence.

错误一：忘记写下结论。即使归纳递推完美，也可能丢分。务必用一个清晰的结论句收尾。

Mistake 2: Using the inductive hypothesis without stating it. Examiners want to see 'Assume P(k) is true' explicitly.

错误二：在没有陈述归纳假设的情况下使用它。考官希望明确看到"假设 P(k) 为真"。

Mistake 3: Algebraic blunders when expanding or factoring in the inductive step. Practise factorising expressions involving k+1 carefully.

错误三：归纳递推过程中展开或因式分解时出现代数错误。要有针对性地练习对含有 k+1 的表达式进行因式分解。

imes n=1 may not be the smallest valid value; read the question to confirm the starting n.

错误四：没有彻底检验基础情形。有时 n=1 未必是最小的有效值；阅读题目以确认起始的 n。

Mistake 5: Assuming P(k+1) is true before proving it. You must derive it from P(k), not assume the result and work backwards incorrectly.

错误五：在证明之前就假设 P(k+1) 为真。你必须从 P(k) 将其推导出来，而不是反过来先假定结果再错误地倒推。

---

12. Summary and Exam Tips | 总结与应试技巧

Proof by induction is a guaranteed exam question if you prepare it well. Memorise the four-step structure, and practise at least two examples of each type: summation, divisibility, and recurrence relations.

数学归纳法只要准备充分，就是一道必拿分的考题。牢记四步结构，并针对每一类型（求和、整除和递推关系）至少练习两道例题。

Always present your work clearly, with one step per line, and label 'Base case', 'Inductive hypothesis', etc. This makes it easier for the examiner to award method marks even if a small slip occurs.

始终清晰地展示你的过程，每行一步，并标注"基础情形""归纳假设"等。这样即使出现小失误，考官也更容易给出方法分。

and P(k) → P(k+1) keeps it going. Induction then becomes a reliable friend, not a mystery.

最后，用多米诺骨牌类比来检验你的逻辑：P(1) 开启了链条，P(k) → P(k+1) 使链条延续。这样一来，归纳法就变成了一个可靠的朋友，而非一个谜团。

---

Published by TutorHao | Mathematics Revision Series | aleveler.com

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