Proof by Induction Extended to Other Areas of Mathematics | 数学归纳法在其他数学领域的延伸

📚 Proof by Induction Extended to Other Areas of Mathematics | 数学归纳法在其他数学领域的延伸

Mathematical induction is a powerful proof technique used to prove statements about infinitely many natural numbers. While it is often introduced through summation formulas, its applicability reaches into many branches of mathematics, including divisibility, inequalities, recurrence relations, matrices, combinatorics, and geometry. Understanding how to extend induction beyond simple sums is essential for A-Level Mathematics, especially in the AQA specification where these extended applications are frequently examined.

数学归纳法是一种用于证明关于无穷多个自然数命题的强大证明技术。虽然通常在求和公式中引入，但它的应用范围深入数学的许多分支，包括整除性、不等式、递推关系、矩阵、组合数学和几何。理解如何将归纳法扩展到简单求和之外，对于A-Level数学至关重要，尤其是在AQA大纲中，这些扩展应用经常被考查。

---

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

To prove a statement P(n) for all positive integers n, we establish two steps. The base case verifies P(1) (or P(k) for some starting value). The inductive step assumes P(k) is true for some arbitrary k ≥ 1 and shows that P(k+1) follows. Together, these two steps imply that P(n) is true for all n ≥ 1.

为了证明命题 P(n) 对所有正整数 n 成立，我们需要确立两个步骤。基础情况验证 P(1)（或某个起始值 P(k)）。归纳步骤假设 P(k) 对某个任意 k ≥ 1 成立，并推出 P(k+1) 也成立。两者结合即可推出 P(n) 对所有 n ≥ 1 成立。

The key lies in the inductive hypothesis: we assume P(k) is true and use it as a stepping stone. The chain of implications then covers every natural number. This can be expressed symbolically as:

关键在于归纳假设：我们假设 P(k) 成立，并以此为跳板。这个蕴含链于是覆盖每一个自然数。这可以用符号表示为：

P(1) ∧ (∀k ≥ 1, P(k) ⇒ P(k+1)) ⇒ ∀n ≥ 1, P(n)

---

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

Divisibility statements are a classic area where induction shines. For example, prove that 3²ⁿ⁺¹ + 2ⁿ⁺² is divisible by 7 for all integers n ≥ 1.

整除性命题是归纳法大显身手的经典领域。例如，证明对所有整数 n ≥ 1，3²ⁿ⁺¹ + 2ⁿ⁺² 能被 7 整除。

Base case: when n = 1, 3³ + 2³ = 27 + 8 = 35, which is divisible by 7.

基础情况：当 n = 1 时，3³ + 2³ = 27 + 8 = 35，可被 7 整除。

Assume the statement is true for n = k, so 3^2k+1 + 2^k+2 = 7m for some integer m. We want to prove it for n = k+1. Consider 3^2(k+1)+1 + 2^(k+1)+2 = 3^2k+3 + 2^k+3.

假设命题对 n = k 成立，即 3^2k+1 + 2^k+2 = 7m（m 为某个整数）。我们要证明对 n = k+1 也成立。考虑 3^2(k+1)+1 + 2^(k+1)+2 = 3^2k+3 + 2^k+3。

Rewrite the expression using the inductive hypothesis. Note that 3^2k+3 = 9 · 3^2k+1 and 2^k+3 = 2 · 2^k+2. Then the expression becomes 9 · 3^2k+1 + 2 · 2^k+2. Since 3^2k+1 = 7m − 2^k+2, substituting gives:

利用归纳假设改写表达式。注意 3^2k+3 = 9 · 3^2k+1，2^k+3 = 2 · 2^k+2。于是表达式变为 9 · 3^2k+1 + 2 · 2^k+2。因为 3^2k+1 = 7m − 2^k+2，代入可得：

9(7m − 2^k+2) + 2 · 2^k+2 = 63m − 9 · 2^k+2 + 2 · 2^k+2 = 63m − 7 · 2^k+2 = 7(9m − 2^k+2)

Hence the expression is divisible by 7. The key is to express the (k+1)-th case in terms of the k-th case and manipulate the algebra carefully.

因此该表达式可被 7 整除。关键是将第 k+1 种情形用第 k 种情形表达，并进行细致的代数变形。

---

3. Induction for Inequalities | 归纳法处理不等式

Induction can also prove statements about inequalities for all sufficiently large integers. A standard example is n! > 2ⁿ for all n ≥ 4.

归纳法也可以证明关于所有足够大的整数的不等式。一个标准例子是：对所有 n ≥ 4，n! > 2ⁿ。

Base case: n = 4 gives 4! = 24 > 16 = 2⁴, which is true.

基础情况：n = 4 时，4! = 24 > 16 = 2⁴，成立。

Assume k! > 2^k for some k ≥ 4. For k+1, we have (k+1)! = (k+1) · k! > (k+1) · 2^k. Since k ≥ 4, we know k+1 > 2, so (k+1) · 2^k > 2 · 2^k = 2^k+1. Therefore (k+1)! > 2^k+1. By induction, the statement holds for all n ≥ 4.

假设对某个 k ≥ 4，k! > 2^k。考虑 k+1：(k+1)! = (k+1) · k! > (k+1) · 2^k。因为 k ≥ 4，所以 k+1 > 2，于是 (k+1) · 2^k > 2 · 2^k = 2^k+1。因此 (k+1)! > 2^k+1。由归纳法，命题对所有 n ≥ 4 成立。

In inequality proofs, the inductive step often requires an extra comparison, such as k+1 > 2, to bridge the gap between the assumed inequality and the desired one.

在不等式证明中，归纳步骤常常需要额外的比较，例如 k+1 > 2，来架起假设不等式与目标不等式之间的桥梁。

---

4. Induction with Recurrence Relations | 归纳法与递推关系

Many sequences are defined by recurrence relations, and induction is ideal for proving closed-form formulas. For example, define u₁ = 1 and uₙ₊₁ = 2uₙ + 1. Prove that uₙ = 2ⁿ − 1.

许多数列由递推关系定义，而归纳法非常适合证明其通项公式。例如，定义 u₁ = 1，uₙ₊₁ = 2uₙ + 1。证明 uₙ = 2ⁿ − 1。

Base case: u₁ = 1 = 2¹ − 1, so the formula is true for n = 1. Assume u_k = 2ᵏ − 1 for some k ≥ 1. Then from the recurrence relation, uₖ₊₁ = 2u_k + 1 = 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1. Hence the formula holds for k+1. By induction, uₙ = 2ⁿ − 1 for all n ≥ 1.

基础情况：u₁ = 1 = 2¹ − 1，因此公式对 n = 1 成立。假设对某个 k ≥ 1 有 u_k = 2ᵏ − 1。根据递推关系，uₖ₊₁ = 2u_k + 1 = 2(2ᵏ − 1) + 1 = 2ᵏ⁺¹ − 1。因此公式对 k+1 成立。由归纳法，对所有 n ≥ 1 有 uₙ = 2ⁿ − 1。

Notice how the recurrence relation itself supplies the transition from k to k+1, making the inductive step almost mechanical once the closed form is guessed.

注意递推关系本身就提供了从 k 到 k+1 的递推过程，一旦猜出通项公式，归纳步骤几乎是机械的。

---

5. Induction for Matrix Powers | 归纳法求矩阵幂

In AQA A-Level Mathematics, induction is often used to prove formulas for powers of matrices. Suppose A is the matrix [[2,1],[0,1]]. Prove that Aⁿ = [[2ⁿ, 2ⁿ − 1],[0,1]] for all n ≥ 1.

在 AQA A-Level 数学中，归纳法常用于证明矩阵幂的公式。设 A = [[2,1],[0,1]]。证明对所有 n ≥ 1，Aⁿ = [[2ⁿ, 2ⁿ − 1],[0,1]]。

Base case: for n = 1, A¹ = [[2,1],[0,1]], which matches [[2¹, 2¹ − 1],[0,1]]. Assume the formula holds for k, so Aᵏ = [[2ᵏ, 2ᵏ − 1],[0,1]]. Then Aᵏ⁺¹ = AᵏA = [[2ᵏ, 2ᵏ − 1],[0,1]] multiplied by [[2,1],[0,1]].

基础情况：n = 1 时，A¹ = [[2,1],[0,1]]，与 [[2¹, 2¹ − 1],[0,1]] 一致。假设公式对 k 成立，即 Aᵏ = [[2ᵏ, 2ᵏ − 1],[0,1]]。则 Aᵏ⁺¹ = AᵏA = [[2ᵏ, 2ᵏ − 1],[0,1]] 乘以 [[2,1],[0,1]]。

Perform the matrix multiplication: top-left: 2ᵏ · 2 + (2ᵏ − 1) · 0 = 2ᵏ⁺¹; top-right: 2ᵏ · 1 + (2ᵏ − 1) · 1 = 2ᵏ⁺¹ − 1; bottom-left: 0 · 2 + 1 · 0 = 0; bottom-right: 0 · 1 + 1 · 1 = 1. Hence Aᵏ⁺¹ = [[2ᵏ⁺¹, 2ᵏ⁺¹ − 1],[0,1]]. Induction completes the proof.

进行矩阵乘法：左上：2ᵏ · 2 + (2ᵏ − 1) · 0 = 2ᵏ⁺¹；右上：2ᵏ · 1 + (2ᵏ − 1) · 1 = 2ᵏ⁺¹ − 1；左下：0 · 2 + 1 · 0 = 0；右下：0 · 1 + 1 · 1 = 1。因此 Aᵏ⁺¹ = [[2ᵏ⁺¹, 2ᵏ⁺¹ − 1],[0,1]]。归纳法完成证明。

Matrix multiplication must be carried out carefully, and the inductive hypothesis must be applied exactly as stated.

矩阵乘法必须仔细进行，并且归纳假设必须严格按陈述的形式使用。

---

6.

Published by TutorHao | A-Level Mathematics Revision Series | aleveler.com

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