数学归纳法

官官方数学老师·15 页·深入（追求细节与边界）·0 次浏览·2 天前

✦ 数学归纳法数学数学归纳法归纳奠基

数学证明递推思想边界与反例

数学归纳法

搞清两步证明的严格形式、看穿典型反例、厘清归纳法适用边界

按空格/→ 演示下一步

1 / 15 页

全部页面点击任意一页，跳回舞台从这页播放

数学证明递推思想边界与反例

数学归纳法

搞清两步证明的严格形式、看穿典型反例、厘清归纳法适用边界

1第 1 页 · 数学归纳法

从多米诺骨牌说起

上一页我们把数学归纳法定性为「证明技术」。它到底怎么证明?为什么管用?先摆一排多米诺骨牌,让直觉先到位。

起点成立

验证 n=1 时命题为真,像第一块骨牌能被推倒

传递成立

假设 n=k 成立,推出 n=k+1 也成立

覆盖全体

起点加传递两步合一,命题对所有自然数成立

多米诺骨牌对应 →数学归纳法

推倒第 k 块就会撞倒第 k+1 块,加第一块能倒,整排都倒

2第 2 页 · 从多米诺骨牌说起

数学归纳法的逻辑结构

两步证明无限序列的全貌

数学归纳法的逻辑结构

两步证明无限序列的全貌

3第 3 页 · 数学归纳法的逻辑结构

归纳奠基：起点成立

上一页的多米诺骨牌逻辑有一个隐藏前提：第一张必须真的被人推倒。如果第一张没倒，再精巧的连锁设计也是空谈。这个「推倒第一张」的动作，就是归纳奠基。

奠基的本质

直接验证 P(n₀) 为真，不依赖任何归纳推理

起始值 n₀ 的选择

通常取 1，也可取 0、2 或任何使命题有意义的最小值

验证手段

代入法——把 n₀ 代入，等式或不等式必须成立

奠基失败的代价

整个证明从起点断裂，后续归纳步骤形同虚设

推倒第一张多米诺骨牌对应 →P(n₀) 成立

起点不倒，后续无论摆得多整齐，链条都不会启动

P(n_0) = \text{True}

4第 4 页 · 归纳奠基：起点成立

归纳递推：传递链条

奠基解决"第一块骨牌倒下"的问题，但只倒一块永远到不了终点。我们需要一种机制：让"这一步成立"自动推出"下一步也成立"。这就是归纳递推。

归纳假设

假设 P(k) 成立，作为已知条件使用

证明 P(k+1)

由 P(k) 与题设，推出 P(k+1) 也成立

通用性

推导对一切 k≥n₀ 都适用，链条逐节传递

接力赛对应 →归纳递推

每棒只递给下一人，只要每棒都成功，终点必达

P(k) \Rightarrow P(k+1)

5第 5 页 · 归纳递推：传递链条

完整证明的书写规范

一个规范的归纳法证明分五步书写，每步都有固定的位置与作用。

明确命题

用 P(n) 写出要证的「对所有 n 成立」的命题

验证基础

代入最小的 n（通常 n=1），手算确认 P(1) 成立

归纳假设

假设 P(k) 成立，写在递推之前作为已知条件

递推证明

从 P(k) 推出 P(k+1)，这是证明的核心

写下结论

明确写出「由数学归纳法可知，原命题对所有 n 成立」

6第 6 页 · 完整证明的书写规范

什么是递推关系

食堂打饭排长队，想知道排第 10 个人前面有几个人。最笨是从头数到 10；聪明的办法是——第 n 个位置前面的人数 = 第 n-1 个位置的人数 + 1。这就是递推：用前一项算出后一项。

初始值

递推的种子；k 阶递推至少需要 k 个初值才能唯一确定数列

递推规则

一个等式规定 aₙ 如何由前若干项算出

阶数

aₙ 依赖几个前项：只看 aₙ₋₁ 是一阶，看 aₙ₋₁、aₙ₋₂ 是二阶

工资每年涨固定比例对应 →递推关系

明年工资 = 今年的工资 × (1+增长率)，只看最近那项

a_n = a_{n-1} + a_{n-2}, \quad a_1=a_2=1

7第 7 页 · 什么是递推关系

递推关系与归纳假设

上一页我们看到了递推关系的样子，比如 F(n)=F(n-1)+F(n-2)。但递推关系自己不会跑起来——它需要归纳假设往里「喂」原料。这一页要追问：假设和递推，到底是怎么对应的？

归纳假设

把 P(k) 临时当成已知「原料」，不是要证的结论本身

递推关系

命题里自带的结构，负责把 P(k) 加工成 P(k+1)

精确对接

假设的输出必须正好是递推的输入，差一项就推不下去

边界提醒

假设只在递推这一步有效；递推不能脱离原命题临时编造

工厂装配线对应 →假设与递推

假设是上一站送来的合格零件，递推是本站把它加工成下一零件的操作规范

P(k) \xrightarrow{\;\text{递推关系}\;} P(k+1)

8第 8 页 · 递推关系与归纳假设

数学归纳法vs完全归纳法

两者仅一字之差，却一个管无穷、一个管有限——选错工具，证明从一开始就立不住。

数学归纳法

面向无穷集合：对全体自然数 n 成立
两步结构：奠基 P(1) + 递推 P(k)→P(k+1)
逻辑基础：良序原理 / Peano 公理
只证一次递推，无穷步自动成立

完全归纳法

面向有限集合：对编号 1 到 N 成立
一步结构：把 N 个情形逐一验证
逻辑基础：有限枚举，无需公理
举完即止，N 之外一概不管

证「所有 n」只能用数学归纳法；命题只到 N 时穷举更直观，但穷举永远跨不过无穷。

9第 9 页 · 数学归纳法vs完全归纳法

第一数学归纳法vs第二数学归纳法

推到 P(k+1) 卡住？两个版本假设强度不同，用错会让证明卡壳。

第一数学归纳法

假设：仅 P(k) 成立
推出：P(k) → P(k+1)
适用：递推只看前一步
局限：前一步信息不足时证不下去

第二数学归纳法（强归纳）

假设：P(n₀),…,P(k) 全成立
推出：全部前期 → P(k+1)
适用：递推需前多步信息
优势：复杂递推写起来更顺手

先试第一归纳法；证到 P(k+1) 卡住时改用强归纳；两者逻辑等价，只是假设范围不同。

10第 10 页 · 第一数学归纳法vs第二数学归纳法

等差数列的递推定义

上页我们比较了第一与第二数学归纳法。要真正用归纳法证明数列命题,得先把数列本身用递推的方式严格定义出来——否则归纳链条无从下手。

首项 a₁

数列第一项,递推的起点,对应归纳奠基的位置

公差 d

相邻两项的固定差,决定数列整体走向

递推式

aₙ₊₁ = aₙ + d,由前一项唯一确定后一项

唯一确定

首项和公差一旦给定,整个数列就被锁死

上楼梯对应 →等差数列递推

第一级台阶对应首项,每级抬升 d 对应公差,知道起点和步高,整段楼梯就定了

\begin{cases} a_1 = a \\ a_{n+1} = a_n + d \end{cases} \ (n \geq 1)

11第 11 页 · 等差数列的递推定义

归纳法证明等差数列通项

把归纳法的三步走套到等差数列上，推导an=a1+(n-1)d的完整证明。

奠基：n=1

代入n=1，右边=a1+0·d=a1，与左边的a1相等。

假设n=k

设ak=a1+(k-1)d成立，作为递推的起点。

递推n=k+1

由a(k+1)=ak+d与假设，得a1+(k-1)d+d=a1+kd。

下结论

奠基与递推均成立，公式对一切正整数n成立。

12第 12 页 · 归纳法证明等差数列通项

自测：哪一步出了问题

点击作答

用数学归纳法证明'1+2+...+n=n(n+1)/2'时，奠基验证 n=1 成立。递推时假设 n=k+1 成立，再证 n=k 也成立。这个证明错在哪里？

13第 13 页 · 自测：哪一步出了问题

知识结构图

✓桥接原理：用有限步验证支撑无穷结论，奠基与递推缺一不可
✓变体差异在归纳假设的强度：第一归纳 < 第二归纳 < 完全归纳
✓递推关系是归纳法的'语言'：先有递推结构，才有归纳可用
✓错误高发在'假设越界'：用错前提或奠基遗漏是常见陷阱
✓本质是良序性的有限投影：自然数可被逐个'点亮'

延伸主题：良序原理与归纳法等价归纳法证算法正确性超限归纳法初探

14第 14 页 · 知识结构图

课后思考

先独立思考再对比参考答案。三个问题分别对应：回看骨架、动手复盘、看清边界。

1数学归纳法中，'奠基'和'递推'为什么缺一不可？如果只用其中一步，证明会出什么问题？

参考答案奠基是链条的根，保证 n=1 起点成立；递推是链节，保证每个 n+1 都能从 n 接力。仅奠基只证孤立起点；仅递推则链条悬空。归纳法就是'有根的链'，缺一不可。

2用归纳法证明 1+2+...+n = n(n+1)/2 时，递推步最关键的变形是什么？为什么想到这样变形？

参考答案关键是把 S(k+1) 拆成'前 k 项 + 第 k+1 项'，用归纳假设把前 k 项替换为 k(k+1)/2，再合并化简。这是'拆分—代换—合并'三步：递推假设是已知路标，拆分搭桥过去。

3第二数学归纳法的假设'前面所有 k<n 都成立'，比第一归纳法只假设 k=n 成立更强吗？两者能证明同一类命题吗？

参考答案假设更强不等于能证的命题更多——两类归纳法等价，能用第二归纳法证的，第一归纳法也能证；反之亦然。第二归纳法在递推依赖'前缀条件'时书写更自然。

15第 15 页 · 课后思考