T(0) = 1，T(1) = 0，T(n )= 2* T(n-2)的递推关系

Question

我试图找出上述表达式的重复关系。

我推断：

T(n) = C*T(n-2)

T(n-2) = 2C*T(n-4)

T(n-4) = 3C * T(n-6)

..。

T(n) = k/2C *T()

我被困在这里了。这是正确的做法吗？简化方程中没有T的简化递推关系是什么？

Answer 1

让我们在扩展此函数的m时间时观察其行为：

T(n) = 2^2 * T(n - 2*2)
     = 2^3 * T(n - 2*3)
     = 2^4 * T(n - 2*4)
     = ...
     = 2^m * T(n - 2m)

当n是：

• 偶数：n - 2m最终等于零，这意味着最大值是m = n / 2，而T(n) = 2^(n/2)
• 奇数：“最终等于1，这意味着T(n) = 2^(...) * T(1) = 0

如果我们想把它写在一个表达式中：

T(n) = (1 - n + floor[n/2]) * 2^(n/2)

Answer 2

我编写了一个python程序并发现了这种关系：

def rec(num):
    if num == 0:
        return 1
    elif num == 1:
        return 0
    else:
        return 2 * rec(num - 2)

经过几次测试，我发现了这样的规则：

指数2，3，4，5，6，7，8. 结果2，0，4，0，8，0，16…

因此，当n= 2k &0时，当n= 2k +1 (k属于Z)时，结果可能是2^(n/2)。