※ 引述《roger00 (Stage Column(?))》之铭言：
: 助教你好,最近做证明题有一些问题,不知道能否为我解答?谢谢!
: (i) 为什么数学归纳法是正确的?
: (ii) 数学归纳法使用上有两种:
: Type A 当 n= c1,c2 时,叙述成立 (先试几个实例)
: 假设 n= k 时,叙述成立
: 推到 n= k+1 叙述亦成立,则 对于所有c1,c2以上的正整数 叙述都成立
: Type B 当 n= c1,c2 时,叙述成立 (先试几个实例)
: 假设 n<= k-1 时,叙述成立
: 推到 n= k 叙述亦成立,则 对于所有c1,c2以上的实数 叙述都成立
: 这两种分别是离散型和连续型的数学归纳法,两种证明方式都是正确的吗?
(i)
可以把数学归纳法看成是逻辑推论的结果.
如你所言,数学归纳法有2个主要的部份
我们若想証明 P(n) is true for all integers n with n>=n0 这件事,
可以利用証明以下2件事达成
(1) the base step: P(n0) is true.
(2) the induction step:
"P(n) is true" => "P(n+1) is true", for all integers n with n>=n0
那么借由不断地套用(2), 我们可以知道
"P(n0) true" => "P(n0+1) true" => .......
但是这只是一种型式, 你也可以借由証明
(1) "P(n0) is true" and "P(n0+1) is true"
(2) "P(n) is true" => "P(n+2)" is true", for all n>=n0
来得到一样的结论
总归一句, 将它视为逻辑上的结论
若你问的是更根本的理由, 数学归纳法在正整数上会成立,
是因为正整数满足well-ordering principle
(任何非空的正整数集合, 都可以找到当中一个最小的元素)
换句话说, 任何其它具有这种特性的结构, 你都可以在它上面套用数学归纳法
(例如负整数, 每个负整数集合你都可以找到一个当中最大的元素)
(ii)
这里的Type B不太正确唷, 理由是我们没办法由Type B里的base step及induction step
得到你所提的结论