math - 有人可以解释数学归纳法(证明递归方法)

有人可以解释数学归纳法以证明递归方法吗？我是计算机科学专业的新生，并且还没有修过微积分(我已经通过Trig学习过)。我有点理解，但是当被问到为递归方法写归纳证明时，我遇到了麻烦。

最佳答案

这是一个示例说明:

假设您要证明以下公式:

sum(i | i <- [1, n]) = n * (n + 1) / 2

此公式为1和n之间的所有整数的和提供了封闭形式。

我们将从证明n = 1的简单基本案例的公式开始。在这种情况下，公式的两面都简化为1。这又意味着该公式适用于n = 1。

接下来，我们将证明，如果该公式对n值有效，则对下一个n(或n + 1)值有效。换句话说，如果满足以下条件:

sum(i | i <- [1, n]) = n * (n + 1) / 2

那么以下内容也适用:

sum(i | i <- [1, n + 1]) = (n + 1) * (n + 2) / 2

为此，让我们从最后一个公式的第一侧开始:

s1 = sum(i | i <- [1, n + 1]) = sum(i | i <- [1, n]) + (n + 1)

也就是说，1和n + 1之间的所有整数之和等于1和n之间的整数之和，加上最后一项n + 1。

由于我们以该公式适用于n的条件为基础证明，因此我们可以这样写:

s1 = n * (n + 1) / 2 + (n + 1) = (n + 1) * (n + 2) / 2 = s2

如您所见，我们已经到达了要证明的公式的第二侧，这意味着该公式确实成立。

这样就完成了归纳证明，但实际上是什么意思呢？

该公式对于n = 0是正确的。

如果该公式对于n是正确的，那么它对于n + 1是正确的。

从1和2，我们可以说:如果公式对于n = 0是正确的，那么对于0 + 1 = 1是正确的。既然我们证明了n = 0的情况，那么n = 1的情况确实是正确的。

我们可以再次重复以上过程。 n = 1的大小写是正确的，然后n = 2的大小写是正确的。这种推理可以无限进行。该公式对于n> = 1的所有整数值都是正确的。

关于math - 有人可以解释数学归纳法(证明递归方法)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/866407/