ZT：出轨-组合数学

读了答案真是粉特了。。。。。老美的解答写出来还真是罗嗦啊。。。。有没有纯公式版的呀。。。。我貌似从前接触过这道题的，貌似见过很多> and < 的版本。。。。

另外strong induction/weak induction是什么意思啊 ...
小K 发表于 2010-2-25 07:04

老美就是怕你不懂，所以狂举例子……
后面那部分也把我看得有点粉特，估计纯公式我能看得舒服点=.=

读了答案真是粉特了。。。。。老美的解答写出来还真是罗嗦啊。。。。有没有纯公式版的呀。。。。我貌似从前接触过这道题的，貌似见过很多> and < 的版本。。。。

另外strong induction/weak induction是什么意思啊 ...
小K 发表于 2010-2-25 07:04

我记得没错的话，strong induction是 m<n 所有的p(m)都要true，那p(n)是true。weak induction是只要 p(n)是true，那p(n+1)也是true。两者貌似是几乎一样的，就只有做法上不同。有些时候Weak induction很好用，特别是如果p只涉及到n和n+1的话，而strong induction一般用在p涉及到n之前所有的Element。

我记得没错的话，strong induction是 m
edwardgtxy 发表于 2010-2-25 18:10

对。Strong就是要用之前所有的statements "P(0) is true, P(1) is true.....P(n-1) is true"来推出 P(n) is true.
Weak是用P(n-1) is true推出 P(n) is true.
其实都是ok的，weak算是strong的一个特例吧～

有趣，感谢zach & edward的解释。
有没有什么例子是只能用strong induction证明，不能用weak induction的？
另外，恕我老年痴呆，不知道我记错了没有哈，数学归纳法不是国内初中学的么？

有趣，感谢zach & edward的解释。
有没有什么例子是只能用strong induction证明，不能用weak induction的？
另外，恕我老年痴呆，不知道我记错了没有哈，数学归纳法不是国内初中学的么？
小K 发表于 2010-2-25 22:53

使用归纳法，应该在高中讲数列涉及了一些，但是理论上的知识，还得大学。而且大多数专业都不学离散数学……只有CS、CE、通讯什么的才会学……貌似有的大学可以自由选，但是也只有这几个能用到的专业的娃娃才会选吧……～
weak和strong是等价的。我没有学过离散数学，凑合证一下……

有一个起点a(为了方便起见，令a=0)，有一个性质P，
对strong induction更完整的表述如下：
如果对任意的n都满足“只要P(0)～P(n-1)成立，P(n)就一定成立”，那么我们就知道性质P对所有的自然数都成立了。

对weak induction更完整的表述如下：
如果对任意的n都满足“只要P(n-1)成立，P(n)就一定成立”，那么我们就知道性质P对所有的自然数都成立了。

也就是说，weak和strong都是方法，只要能用strong证明，就说明P对所有的自然数都成立。那么自然对任意的n都满足“P(n-1)成立，P(n)就一定成立”，因此也满足weak。


希望说明白了……

感谢解释
好像明白了。我果然没学过离散数学。。。

strong induction　的使用是因为假设P(0) ~ P(n-1)都成立的时候，with more assumptions it may be easier to prove P(n)

离散数学一般应用在什么地方呢？in layman's terms...

感谢解释
好像明白了。我果然没学过离散数学。。。

strong induction　的使用是因为假设P(0) ~ P(n-1)都成立的时候，with more assumptions it may be easier to prove P(n)

离散数学一般应用在什么 ...
小K 发表于 2010-2-26 00:43

对的，这两个只是方法的区别。像Edward说的，在只涉及n和n-1的问题里，weak简单点，如果涉及了n之前所有的东西的问题，用strong方便。attach了一个公式版的证明strong和weak等价的pdf，貌似小K姐姐喜欢公式版～我怕我讲不明白，呵呵～ induction.pdf (42.44 KB, 下载次数: 4)

2010-2-26 01:00 上传

点击文件名下载附件
下载积分: 大米 -1 颗

(该证明版权归CMU的CS系Prof. Victor Adamchik所有)

至于用在什么地方，召唤学过的同学放解吧……我也没学过=.=

果然还是公式简洁亲切。

一起等解释～～～～～～～～～

想想，很多学科／小分支用layman's term解释一下在平时生活里面的应用都应该挺有意思的啊
端木在统计版贴过很多次～～～

果然还是公式简洁亲切。
小K 发表于 2010-2-26 01:11

是啊，感觉他这个证明真巧～比我那blabla说了半天 好懂多了……

zach把昨天edward贴的证明写成公式吧