第 5 章归纳与递归¶

章节导引

本页从《离散数学讲义》拆分而来，保留原章节锚点，方便从旧总览页和旧链接跳转。

学习目标¶

能用归纳证明处理整数命题、递归结构和递归算法正确性。

前置知识¶

第 1 章证明方法、第 2 章序列与递推，以及基本函数/算法语言。

建议用时¶

建议 4–6 小时：普通归纳 2 小时，强归纳 1–2 小时，递归结构与算法 1–2 小时。

练习建议¶

完成 2 个数学归纳证明；用强归纳证明一个分解类命题；为一个递归定义写出前几项。

参考资料与引用边界¶

整理者：Lumner。
课程来源：根据 DM/ 目录下的课件整理；本章对应课件：DM5.1-5.4(7).pdf。
原始讲义文件：note/离散数学讲义.md。
引用边界：这是公开学习笔记，不替代课程正式教材、教师课件或考试要求；外部引用时请注明来自本网站整理版。

5.0 核心目标¶

归纳法用于证明关于整数的无限命题；递归用于定义对象、函数和算法。二者相互支撑：递归结构通常用归纳证明性质，递归算法常用归纳证明正确性。

5.1 数学归纳法¶

第一数学归纳原理¶

若：

\(P(1)\) 为真。
对任意 \(k\ge1\)，\(P(k)\to P(k+1)\) 为真。

则：

\(\forall n\in\mathbb Z^+\,P(n)\)

更一般地，若从 \(n_0\) 开始证明，则基例为 \(P(n_0)\)，归纳步证明 \(P(k)\to P(k+1)\) 对所有 \(k\ge n_0\) 成立。

归纳证明模板¶

要证明对所有 \(n\ge b\)，\(P(n)\) 成立：

明确写出命题 \(P(n)\)。
基础步：证明 \(P(b)\)。
归纳假设：假设 \(P(k)\) 对某个任意 \(k\ge b\) 成立。
归纳步：在归纳假设下证明 \(P(k+1)\)。
结论：由数学归纳法，命题对所有 \(n\ge b\) 成立。

为什么归纳法有效¶

归纳法基于良序性质：每个非空正整数集合都有最小元素。

若存在反例，则反例集合非空，设最小反例为 \(m\)。由于基例成立，\(m>b\)。则 \(m-1\) 不是反例，\(P(m-1)\) 成立。由归纳步推出 \(P(m)\) 成立，矛盾。

例：有限集子集个数¶

命题：若 \(S\) 有 \(n\) 个元素，则 \(S\) 有 \(2^n\) 个子集。

基例：\(n=0\) 时，\(S=\varnothing\)，只有一个子集，\(1=2^0\)。

归纳步：假设任意 \(k\) 元集合有 \(2^k\) 个子集。设 \(S\) 有 \(k+1\) 个元素，取出一个元素 \(a\)，令 \(T=S-\{a\}\)。\(T\) 有 \(k\) 个元素。

\(S\) 的子集分两类：

不含 \(a\)：对应 \(T\) 的子集，有 \(2^k\) 个。
含 \(a\)：由 \(T\) 的每个子集加上 \(a\) 得到，有 \(2^k\) 个。

总数为 \(2^k+2^k=2^{k+1}\)。

5.2 强归纳与良序性¶

强归纳原理¶

若：

\(P(n_0)\) 为真。
对任意 \(k\ge n_0\)，若 \(P(n_0),P(n_0+1),\ldots,P(k)\) 全部为真，则 \(P(k+1)\) 为真。

则 \(P(n)\) 对所有 \(n\ge n_0\) 成立。

强归纳适用于当前结论依赖多个较小情形的证明。

例：整数的素因子分解存在性¶

命题：每个大于 1 的整数都可写为素数或若干素数的乘积。

用强归纳。对 \(n=2\) 成立。假设 \(2,3,\ldots,k\) 都可分解。考虑 \(k+1\)：

若 \(k+1\) 是素数，结论成立。
若 \(k+1\) 是合数，则 \(k+1=ab\)，其中 \(2\le a,b\le k\)。由强归纳假设，\(a,b\) 都可分解为素数乘积，所以 \(k+1\) 也可。

良序性¶

良序性质：每个非空的非负整数集合都有最小元素。

数学归纳、强归纳和良序性在逻辑上等价，常根据问题选择最方便的形式。

例：除法算法¶

除法算法：对整数 \(a\) 和正整数 \(d\)，存在唯一整数 \(q,r\)，使：

\(a=dq+r,\quad 0\le r<d\)

存在性证明可用良序性：考虑集合 \(S=\{a-dq\mid q\in\mathbb Z,\ a-dq\ge0\}\)。该集合非空，有最小元素 \(r\)。证明 \(r<d\)，否则 \(r-d\) 也是非负且更小，矛盾。

唯一性可假设：

\(a=dq+r=dq'+r'\)

其中 \(0\le r,r'<d\)。则 \(d(q-q')=r'-r\)。右边绝对值小于 \(d\)，而左边是 \(d\) 的倍数，只能为 0，所以 \(r=r'\) 且 \(q=q'\)。

5.3 递归定义与结构归纳¶

递归定义函数¶

递归定义通常包括：

基础步：给出初始值。
递归步：用较小输入的值定义当前值。

阶乘：

\(0!=1\)

\(n!=n(n-1)!\)，\(n\ge1\)

斐波那契数：

\(f_0=0,\ f_1=1\)

\(f_n=f_{n-1}+f_{n-2}\)，\(n\ge2\)

欧几里得算法的递归思想¶

若 \(a=bq+r\)，则：

\(\gcd(a,b)=\gcd(b,r)\)

反复把较大问题转化为较小问题，直到余数为 0。

例：

\(662=414\cdot1+248\)

\(414=248\cdot1+166\)

\(248=166\cdot1+82\)

\(166=82\cdot2+2\)

\(82=2\cdot41+0\)

所以 \(\gcd(662,414)=2\)。

递归定义集合¶

递归定义集合也包含基础步和递归步。

例：集合 \(S\)：

基础步：\(3\in S\)。
递归步：若 \(x\in S\) 且 \(y\in S\)，则 \(x+y\in S\)。

可以证明 \(S\) 是所有 3 的正倍数集合。

字符串集合¶

设字母表为 \(\Sigma\)。所有有限字符串集合 \(\Sigma^*\) 可递归定义：

基础步：空串 \(\lambda\in\Sigma^*\)。
递归步：若 \(w\in\Sigma^*\) 且 \(x\in\Sigma\)，则 \(wx\in\Sigma^*\)。

字符串连接也可递归定义。

合式公式¶

命题逻辑合式公式可递归定义：

基础步：\(T,F\) 和命题变量是合式公式。
递归步：若 \(A,B\) 是合式公式，则 \(\neg A\)、\((A\land B)\)、\((A\lor B)\)、\((A\to B)\)、\((A\leftrightarrow B)\) 是合式公式。

由此可用结构归纳证明：每个合式公式左右括号数量相等。

结构归纳¶

对递归定义的对象集合证明性质：

基础步：证明初始对象满足性质。
递归步：假设用于构造新对象的已有对象满足性质，证明新对象也满足性质。

结构归纳是数学归纳在递归结构上的推广。

树的递归定义¶

有根树可递归定义：

基础步：单个顶点是一棵有根树。
递归步：把若干棵互不相交的有根树接到一个新根下，得到新有根树。

满二叉树可递归定义：

基础步：单个顶点是一棵满二叉树。
递归步：若 \(T_1,T_2\) 是互不相交的满二叉树，则以新根连接 \(T_1,T_2\) 得到满二叉树。

树的高度、顶点数等性质常用结构归纳证明。

5.4 递归算法¶

递归算法定义¶

递归算法通过把问题化为更小规模的同类问题来求解。为了终止，必须最终到达已知解的基础情形。

阶乘递归算法：

procedure factorial(n: nonnegative integer)
    if n = 0 then return 1
    else return n * factorial(n - 1)

最大公约数递归算法：

procedure gcd(a, b: nonnegative integers, a < b)
    if a = 0 then return b
    else return gcd(b mod a, a)

递归算法正确性¶

证明递归算法正确常用归纳法：

证明基础输入上算法正确。
假设较小输入上算法正确。
证明当前输入调用较小输入后也正确。

递归与迭代¶

递归：不断把计算约化为较小实例。

迭代：通过循环重复更新状态。

递归表达更贴近数学定义，但可能有额外调用栈开销；迭代通常更直接控制资源。

递归斐波那契算法¶

procedure fibo(n: nonnegative integer)
    if n = 0 then return 0
    if n = 1 then return 1
    return fibo(n - 1) + fibo(n - 2)

该算法形式简单，但会重复计算大量子问题。后续算法课程可用动态规划优化。

本章小结与后续扩展¶

本章已覆盖数学归纳、强归纳、良序性、递归定义、结构归纳和递归算法。后续可补充更多递归算法复杂度分析，以及动态规划与递归的联系。

第 5 章 归纳与递归¶