归纳推理
guī nà tuī lǐ
归纳推理从观察到的具体例子中形成一般性结论,得到的是大概率成立但并非确定的结果。
Definition
归纳推理是指从若干例子中注意到一个规律，并推断它大概率在一般情形下也成立，是有根据的规律发现，而非确定的证明。它从具体观察出发，得出一个大概率成立但并非确定的一般性结论，一个反例就能推翻一个通过归纳得出的结论；在数学中，归纳推理用来产生猜想，但要证明它们则需要演绎法。在哲学中，归纳问题（休谟问题）问的是为什么过去的规律能证明对未来的预测是合理的；在数学中，归纳推理被归入发现阶段，尽管概率方法（例如施瓦茨-泽佩尔引理）能以量化的误差界限来形式化"大概率成立"的命题。
Example
$1+3=4$，$1+3+5=9$，$1+3+5+7=16$：这个规律暗示前 $n$ 个奇数之和是 $n^2$，这是通过归纳推理得出的一个猜想。但 $n^2 - n + 41$ 对 $n = 0, 1, \ldots, 40$ 都给出素数，诱使人们归纳出"它总是给出素数"的结论，而这是错误的，因为在 $n = 41$ 处结果是 $41^2$，不是素数。米勒-拉宾素性检验使用了类似归纳的概率证据：经过 $k$ 轮之后，一个合数通过检验的概率至多为 $4^{-k}$，在 $k=50$ 时对实际用途来说已几乎确定无疑。
Key Insight
科学家使用归纳推理（实验导向一般性定律）；数学家随后必须用演绎法证明这些规律，才能把它们变成定理。素数生成多项式的例子说明，无论多少个符合的情形都无法证明一个一般性的数学命题，一个反例总是足以推翻它。计算数论经常使用概率性的归纳证据：RSA 密钥生成依赖于概率素性检验而非确定性的素性证明，在确定性与计算成本之间取得平衡。