algorithm - 数学归纳法，如何证明这个递归函数有效

Question

我正在读这本书:The Algorithm Design Manual ，我有一个问题要理解，这是关于归纳假设，所以我有这个伪代码:

Increment(y)
  if y = 0 
    then return(1) 
 else if (y mod 2) = 1 
   then return(2 · Increment(⌊y/2⌋))
  else 
    return(y + 1)

所以我必须通过数学归纳法证明这段代码确实有效，第一部分很简单:

if y = 0 
    then return(1)

最后一部分也很简单，就是取偶数

else 
    return(y + 1)

但是中间部分对我来说很难:

else if (y mod 2) = 1 
   then return(2 · Increment(⌊y/2⌋))

这是本书的解释:

Now, the case of odd y (i.e. y = 2m + 1 for some integer m) can be dealt with as:
(y = 2m + 1; because 2m + 1 is equal to any odd number)//this is what i understand

= 2 · Increment(⌊(2m + 1)/2⌋)//(2m + 1)/2 = m + 1/2
= 2 · Increment(⌊m + 1/2⌋)//ok we get here, but how (m + 1/2) will be the "m" bellow?
= 2 · Increment(m)
= 2(m+1)
= 2m+2 =y+1

谁能解释一下如何证明这个递归真的有效？以及如何通过数学归纳法证明这一点。

Answer 1

= 2 · Increment(⌊m + 1/2⌋) //ok we get here, but how (m + 1/2) will be the "m" bellow?

因为 ⌊m + 1/2⌋ = m ，就这么简单。 (我假设您知道 ⌊m + 1/2⌋ 表示 floor(m + 1/2) 。

请注意 m是一个整数，并且给定 1/2是小数，那么 floor(m+1/2)是m .事实上，floor(m + x) , 其中0 <= x < 1 , 就是 m : 将任何小数部分添加到 m不会改变 floor() 的结果.

所以你得到 2 * Increment(m) = 2(m+1) = 2m+2 = (2m+1)+1 = y+1

更新:归纳证明非常相似。

回顾归纳证明的一般布局:首先，我们阐述归纳假设。然后，我们证明该假设适用于基本情况(通常，基本情况是 n = 0 或 n = 1 时)。最后但同样重要的是，我们使用假设表明，如果它适用于 n 的某个值, 那么它也适用于 n+1 .由于该假设适用于基本情况，并且因为我们证明(通过归纳步骤)如果它适用于 n , 然后它适用于 n+1 ，那么对于大于或等于基本情况值的每个值都必须为真。

假设

在这个特定情况下，我们的假设是这个函数:

I(n) = 1 if n is 0
       n+1 if n is even
       2 * I(floor(n / 2)) otherwise

等于n+1 , 即

I(n) = n+1

在哪里I(n)只是 Increment(n) 的简写符号.您还可以将假设视为一组 3 个数学陈述(换句话说，假设是三种情况中的每一种在所述条件下的计算结果均为 n+1)。

基本案例

基本情况是 n = 0 .对于 n = 0 , I(n)评估为 1 ，即 n+1 (n 为 0)，因此我们已经证明该假设适用于 n = 0。 .

现在，我们要证明如果我们的假设适用于 n , 然后它适用于 n+1 .

诱导步骤

如果I(n) = n+1成立，那么I(n+1) = (n+1)+1一定是真的。基本上，我们是说，“好吧，如果 I(n) 的计算结果是它的参数加一，那么这意味着 I(n+1) 必须是 (n+1)+1 。这就是我们必须证明的:我们必须证明 I(n+1) = (n+1)+1 。

现在，根据 I(n) 的原始定义，我们有两种情况:它的参数要么是偶数，要么是奇数。

这一次，函数的参数 I是n+1 - 让我们考虑这两种情况。

如果n+1是偶数，根据 I(n) 的定义，我们可以立即看到 I(n+1) = (n+1)+1 .

如果n+1是奇数，那么我们知道 n+1 = 2m+1对于某个整数 m ，因为如果 n+1是奇数，那么 n是偶数，表示有一个整数m小于 n这样 2m = n .所以，我们可以重写n+1作为2m+1 :

I(n+1) = I(2m + 1) = 
       = 2 * I(floor((2m+1) / 2)) =
       = 2 * I(floor(m + (1/2)) =
       = 2 * I(floor(m)) = // we can remove 1/2 for the same reason
       = 2 * I(m) =
       = 2 * (m+1) = // inductive step; we used the hypothesis that I(n) = n+1
       = 2*m + 2 = 
       = (2*m+1) + 1 =
       = (n+1) + 1

这表明如果 floor(n/2) 的命题为真(因为 m 是 n/2 )，那么 n+1 也是如此.通过使用 strong induction ，我们可以证明，如果命题对所有 m 都成立，0 <= m <=n，它对 n+1 也成立(见下面的评论)。

所以，确实，I(n+1) = (n+1)+1对于任何整数，假设 I(n) = n+1 有效。

我们表明该假设适用于 n+1如果它适用于 n ，我们证明它适用于 n = 0 .因此，它适用于 n >= 0 .