反向归纳法(Backward Induction)是主要应用于数学学科的一种思维方法和证明命题的方式。
方法
设P(n)表示一个与自然数n有关的命题,若
(1)P(n)对无数多个自然数n都成立;
(2)假设P(k+1)成立,可推出P(k)也成立;
则P(n)对一切自然数n都成立。
证明
用反证法易证反向归纳法原理的正确性:
如果有m满足P(m)不成立,则P(m+1)不成立
可以类推至m之后的任意整数
所以P(n)只可能对比m小的自然数成立
不可能为无限个,矛盾!
所以P(n)对一切自然数n都成立