Ch5 Induction and Recursion

本篇笔记主要介绍了数学归纳法、完全归纳法和结构归纳法的基本概念及其应用，强调了归纳法在证明数学命题中的重要性，并探讨了递归定义与归纳法之间的关系。（由 gpt-4o-mini 生成摘要）

Word Table

演绎(deduce)

1. 数学归纳法 Mathematical Induction

1.1. 导论 Introduction

数学归纳法(mathematical induction) is used to prove propositions of form $\forall n\ P(n)$ where the domain of discourse is the set of positive integers:

P(n_0) \land \forall k\ge n_0 (P(k)\rightarrow P(k+1)) \rightarrow \forall n\ge n_0 (P(n))

更一般的证明过程 More general form of the proof procedure

(1) Basis step: Establish $P(1)$

(2) Inductive step: Prove that $P(k)\rightarrow P(k+1)$ for $k\ge 1$ .

Conclusion: The basis step and the inductive step together imply $\forall n\ P(n)$ .

1.2. 数学归纳法的证明 Proof of Mathematical Induction

良序性(the well-ordering property)：Every non-empty set of non-negative integers has a least element.

Example: Proofs using the well-ordering property

Use the well-ordering property to prove the division algorithm. The division algorithm states that if $a$ is an integer and $d$ is $a$ positive integer, then there are unique integers $q$ and $r$ , with $0\le r<d$ such that $a = dq + r$ .

Answer

The 有效性(validity) of mathematical induction follows from the well-ordering property for the set of positive integers ( $\mathbb{Z}_+$ ).

2. 完全归纳法 Strong Induction

2.1. 导论 Introduction

完全归纳法(strong induction) or 第二数学归纳法(second principle of mathematical induction)：

P(n_0) \land \forall k\ge n_0 (P(n_0) \land P(n_0+1) \land \cdots \land P(k) \rightarrow P(k+1)) \rightarrow \forall n\ge n_0 (P(n))

更一般的证明过程 More general form of the proof procedure

(1) Basis step: Establish $P(n_0)$

(2) Inductive step: Prove $P(n_0) \land P(n_0 + 1) \land \cdots \land P(k) \rightarrow P(k+1)$

Conclusion: The basis step sand the inductive step allow one to conclude that $\forall n\ge n_0 P(n)$ .

Note:

The validities of both mathematical induction and strong induction follow from the well-ordering property. In fact, mathematical induction, strong induction, and well-ordering are all equivalent principles.

2.2. Usages in Computational Geometry

Some Geometry Terms

多边形(polygon)、边(side)、顶点(vertex)
简单多边形(simple polygon)：简单多边形没有边相交。Every simple polygon divides the plane into two regions: its 内部(interior), its 外部(exterior).
对角线(diagonal)：连接任意两个非相邻节点的线段。
内对角线(interior diagonal)：完全在简单多边形内部的对角线。
凸多边形(convex)：凸多边形中的所有对角线均不边相交。或者说，凸多边形一定是简单多边形且所有对角线都是内对角线。
三角剖分(triangulation)：将多边形划分成若干个不重叠的三角形。

具体例题省略，可以自行参考课件。

3. 结构归纳法 Structural Induction

递归(recursion) is a principle closely related to mathematical induction. In a 递归定义(recursive definition), an object is defined in terms of itself.

Sequences, functions and sets that defined recursively is 良定义的(well-defined).

结构归纳法(structural induction) 可以用于递归定义的对象（如树、图）的归纳证明，与数学归纳法有一定相似，但更强调结构的递归性质：

Basis Step: Show that the result holds for all elements specified in the basis step of the recursive definition to be in the set.
Recursive Step: Show that if the statement is true for each of the elements used to construct new elements in the recursive step of the definition, the result holds for these new elements.

TABLE OF CONTENTS

1. 数学归纳法 Mathematical Induction

1.1. 导论 Introduction

1.2. 数学归纳法的证明 Proof of Mathematical Induction

2. 完全归纳法 Strong Induction

2.1. 导论 Introduction

2.2. Usages in Computational Geometry

3. 结构归纳法 Structural Induction

1. 数学归纳法 Mathematical Induction

1.1. 导论 Introduction

1.2. 数学归纳法的证明 Proof of Mathematical Induction

2. 完全归纳法 Strong Induction

2.1. 导论 Introduction

2.2. Usages in Computational Geometry

3. 结构归纳法 Structural Induction

评论