折腾大家一下，如何证明数学归纳法是正确的？

iami_returns

我小时候学归纳法一直疑惑为啥这个数学归纳法是一个正确的推理过程
那位也有和我小时候有一样的问题的吗，你找到答案了吗？

audream

什么意思？你是想证明f(1) = g(1), f(2) = g(2), ..., f(x) = g(x)一定能推出f(x+1) = g(x+1)?

反向证明：如果不正确，那一定可以找到反例。
正向证明：把x+1代进f(x) = g(x)，看成不成立。

暂时想到这么多。

y12345678

。。。。。。引自维基百科


一个简化的证明方法在下面给出。这个证明为了能让 那些没有经过太多数学训练的读者也能够读懂，没有 用到“存在(there exists)”和“对所有元素而言(all)”的数 学符号。这个证明的关键思路是自然数减法和反证法 。

假设：

(1) P(0)

和

(2) 对所有的n ≥ 0, P(n) ⇒ P(n + 1)

这两个命题成立。

考虑如下命题：

(3) 对所有的 m ≥ 0, P(m)成立

就是说对所有m的整数值，P皆为真。

假设此命题为假，即等价于

(4) 存在能使非P(m)成立的m。

此证明试图证明若(1)，(2)为真，可推出(4)为假，从而 得出命题(3)成立。

假设(1)，(2)，(4)命题成立。

由命题(4)，令m′为能使非P(m′)成立的最小值。

显然，m′不能为0，因为这样做会立即导致一个矛盾： (P(0) & 非 P(0)) with P(0) - 与命题(1)矛盾。

假设m′>0

由m′的定义可知，P(m′ - 1)成立，因此由(2)，P(m′)成 立。这也有矛盾：P(m′) & 非 P(m′)同时成立。

因此得出，由(1)，(2)命题只能推出非(4)成立，即前面 所述的命题(3)成立。

因此，有：

(1) P(0)

及

(2) P(n) ⇒ P(n + 1)

成立，可推出（有小小的换元）

(3) 对于所有的 n ≥ 0, P(n)成立。

这个即为数学归纳法原理。

天堂猫

天书。

12oz

y12345678 发表于 2013-9-11 23:51
。。。。。。引自维基百科

理工的应该全部学过，不用纪委。

黑白无常

这要看你的“对”是什么标准。
归纳逻辑是从特殊到一般的推理，这种模式本身具有概率性。
它的提出是对演绎逻辑的补充。
如果你想追求从特殊到一般的归纳必须100%成立，
那是你的心理追求确定性的冲动。

tas

与其说是数学，不如说是逻辑。

njustzjj

数学归纳法的推理过程用的是公理，公理无需证明

交易人生

没有，我小时候一听就知道是正确的，从来没有怀疑过。

菜地一块

还是很好理解的吧，主要就是两个部分，一个是证明在第1步正确，一个是证明如果第k步正确，能够推出第k+1步正确。这样的话，就可以证明第1，2，3，...，k+1步都是正确的。因为根据第2条的话，则第1步正确应该可以推出第2步正确，如果第2步正确，可以推出第3步正确……

例如：用数学归纳法证明自然数列1,2,3,...,n的前N项和公式为n(n+1)/2
可以手工带入n=1，得到1（正确）
且假设第k步正确，即n=k时，前k项和为k(k+1)/2
则n=k+1时，前k+1项和为前n项和再加上第k+1，为 k(k+1)/2 + (k+1) = (k+1)((k+1)+1)/2即若第k步成立,可以推出k+1步成立.
证毕

earthengine

这是个很好的问题。直觉上似乎很明显，但要是深究下去有很多深入的内容。首先是自然数是什么？

皮亚诺给出的定义如下：

1. 1 是自然数。
2. 如果n是自然数，n+1也是自然数。
3. 如果一个关于变量p的命题在p=1时成立，且如果在p=n时成立可以推出p=n+1时也成立，则它对所有自然数成立。

其中第3条就是数学归纳法。这就是说，它只是一个定义的问题。

数学归纳法可以推广到超限序数上，只需要改变一下：

假设p的取值范围是一个良序集合，如果一个命题对于p<n的所有情况成立可以推出p=n时成立，则它对p的所有取值成立。

良序集合的意思是它的元素可以比较大小，而且任何一个子集都有唯一一个最小的元素。这样，自然数和它的子集就是良序集合的特殊情况。而这个归纳法其实也可以证明如下：

如果一个命题对于至少一个p值不成立，那么p的取值范围里使这个命题不成立的p值中有一个最小的n。这样，如果有比n更小的p值这个命题必然是成立的。那么根据归纳假设，可以得到这个命题对n成立，与前面的假设矛盾。

Fernando

计算机专业的话很多都学数学分析来着

xyouc

无聊贴

carl181818

伪命题，它的前提就是假设，’假如开始第一步是对的‘，问题是，第一步本身是无本之木，你怎么就肯定是对的呢？后面的推论都建立在假设上，所以根本站不住脚。

在刑事侦破中如果这么推理，没人会认可。

读书的时候问的老师哑口无言。后来为了考试通过，依葫芦画瓢，为了做题目而做题目，姑且承认它是对的。

melmonash

学习下

y12345678

carl181818 发表于 2013-9-13 15:38
伪命题，它的前提就是假设，’假如开始第一步是对的‘，问题是，第一步本身是无本之木，你怎么就肯定是对的 ...

看来楼上同学没有搞清楚讨论的内容

这里讨论的是数学归纳法作为一般证明用途是的有效性，而非其他的某个特定命题的正确与否

亦即，在满足条件
①  f(1)为真；与
② 若f(m)为真，则f(m+1)亦为真

在前两项条件满足的情况下
数学归纳法认为，所有的f(n)为真

这里讨论的是， 这种方法的有效性。

至于f(1)为真，是讨论的先决条件

iami_returns

y12345678 发表于 2013-9-13 18:12
看来楼上同学没有搞清楚讨论的内容

这里讨论的是数学归纳法作为一般证明用途是的有效性，而非其他的某个 ...

感激不尽！
现在就是证明数学归纳法本身是正确的推理过程

iami_returns

carl181818 发表于 2013-9-13 17:38
伪命题，它的前提就是假设，’假如开始第一步是对的‘，问题是，第一步本身是无本之木，你怎么就肯定是对的 ...

这位兄弟也有这个问题呀。同命相怜啊