“数学归纳法”甚普及,可用作体词。
例:加法结合律
定理:对任意自然数 n
、m
、p
,均有:n + (m + p) = (n + m) + p
。
证明:以数学归纳法对 n
分类讨论:
- 对于
n = 0
:
试论:0 + (m + p) = (0 + m) + p
。
由加法之定义,上式显而易见。 - 对于
n = S n'
,其中n'
满足n' + (m + p) = (n' + m) + p
:
试论:(S n') + (m + p) = ((S n') + m) + p
。
由加法之定义,上式等价于:
S (n' + (m + p)) = S ((n' + m) + p)
。
据归纳假设,上式显而易见。证毕。
“结构归纳法”可简称“归纳”,用作谓词。
例:链表联接结合律
定理:对任意链表 l1
、l2
、l3
,均有:(l1 ++ l2) ++ l3 = l1 ++ (l2 ++ l3)
。
证明:归纳讨论 l1
之构造:
- 对于
l1 = []
:
试论:([] ++ l2) ++ l3 = [] ++ (l2 ++ l3)
。
由链表联接之定义,上式显而易见。 - 对于
l1 = n::l1'
,其中l1'
满足(l1' ++ l2) ++ l3 = l1' ++ (l2 ++ l3)
:
试论:((n :: l1') ++ l2) ++ l3 = (n :: l1') ++ (l2 ++ l3)
。
由链表联接之定义,上式等价于:
n :: ((l1' ++ l2) ++ l3) = n :: (l1' ++ (l2 ++ l3)
。
据归纳假设,上式显而易见。证毕。