有人可以解释数学归纳来证明递归方法吗？我是一名新生计算机科学专业的学生,我还没有学过微积分(我已经通过Trig了).我有点理解它但是当我被要求为递归方法写出感应证明时我遇到了麻烦.
Aym*_*ieh 10
这是一个例子的解释:
假设您有以下要证明的公式:
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,那么它是正确的n + 1.从1和2,我们可以说:如果公式对于n = 0是正确的,那么它是正确的0 + 1 = 1.既然我们证明了这一点n = 0,那么情况n = 1确实是正确的.
我们可以再次重复上述过程.情况n = 1是正确的,那么情况n = 2是正确的.这种推理可以无限制地发挥作用; 公式对于n> = 1的所有整数值都是正确的.
感应!=计算!!!
我可以让N个人喝10*N啤酒.
基础案例:1个人
我可以让一个人喝10杯啤酒
给定p(n)的归纳步骤证明p(n + 1)
我可以让我喝醉了10*i啤酒,如果我添加另一个人,我可以让他喝10杯啤酒.因此,我可以让i + 1个人喝10*(i + 1)啤酒.
p(1) - > p(i + 1) - > p(i + 2)... p(inf)
离散数学很容易!