有效性

对于一个正整数集合任何非空子集，必然有最小的元素存在，假定知道 P(1)P(1) 为真，我们可以从 P(k)→P(k+1)P(k)\to P(k+1)
这个依赖于正整数的良序性

良序性公理 Well-Order-Principle

任意一个非空的非负整数集合都有最小元素

数学归纳原理

首先给一个谓词 P:N→BP : \mathbb N \to \mathbb B 且表示 P(n)P(n) 为真对于所有 n∈Nn\in \mathbb N 成立

基础条件 / 边界条件 base case

证明 P(0)P(0) 为真

递推条件 inductive case

这个需要有一个递推的假设，我们写作 inductive hypothesis 或者缩写为 IH
然后证明 (∀n∈N)(P(n)→P(n+1))(\forall n \in \mathbb N)(P(n)\to P(n+1))

除法定理 Division Algorithm

对于 m,n∈Nm, n \in \mathbb N，一定存在唯一的 q,r∈Nq,r\in \mathbb N 并且 0≤r<m0\le r< m 使得 n=qm+rn = qm + r

强归纳法 Strong Induction

base case 的证明思路和一般数学归纳法相近，但是在归纳的时候有逻辑: 对所有不超过 kk 的正整数 jj 而言, $ 为真可以推导出 P(k+1)P(k+1) 也为真

例子1：代数基本定理 （延伸部分）

命题

对 任意非零自然数可以表述为 有限个质数的积

证明

P(1)P(1)： 1 是 0 个质数的积， vacuuous truth
P(n)=⊤→P(n+1)=⊤P(n) = \top \rightarrow P(n+1) = \top 假设对 [1,n][1,n]的情况都有 P(k)=⊤P(k) = \top , 那么对于新的数 n+1n+1, 如果其是

  1. 质数：那么它是1个质数的积
  2. 合数：那么它可以表示为 a×ba\times b, 其中由于 a,b∈[1,n]a,b\in [1,n] 那么他们可以表示为 质数的积，那么两者相乘，n+1n + 1 可以表述为质数的积

例子 2：斐波那契公式

命题

对于第 n 个斐波那契数 FnF_n， 我们有 ϕ=1+52\phi = \frac{1 + \sqrt 5}{2}, ϕˉ=1−52\bar \phi = \frac{1 - \sqrt 5}{2} 使得 Fn=ϕn−ϕˉn5F_n = \frac{\phi^n - \bar\phi^n}{\sqrt{5}}

从归纳法到 递推算法

递推算法就是正向的推导思路，我们使用有限的基础逻辑推导出新的公式

递推定义

首先定义 base case, 然后使用已有的base case 进行组合排列获得新的

例子1：自然数的定义

Base case: 0
Inductive: successor of n 即自然数 n 的下一个数

例子2：运算符号的定义

结构归纳法 Structural Induction

结构归纳法的基础情况比较丰富，包括多个base case，常用于证明树、图、公式等递归结构的性质。

例子1：3的整数倍

递归定义 3 的倍数

  1. 3∈S3\in S
  2. x,y∈S→x+y∈Sx,y\in S\to x+y\in S

请证明：T={n=3k∣k∈N}T =\{n = 3k|k\in \mathbb N\}

1. 证明 S⊂TS\subset T

base case: 3∈S,3∈T3\in S, 3\in T
induction: x,y∈S,x,y∈T→x+y=3k+3k′=3(k+k′)∈Tx,y\in S, x,y\in T\rightarrow x + y = 3k + 3k' = 3(k+k')\in T 证毕

2. 证明 T⊂ST\subset S

base case: 3∈T,3∈S3\in T, 3\in S
induction: x=3k∈T∧x∈S→P(k+1)→3k+3∈Sx = 3k\in T\land x\in S\rightarrow P(k+1) \to 3k + 3 \in S