如何求解递归T(n)=T(n-1)+T(n-3)-T(n-4),n>=4

Question

如何求解递归方程

1.T(n)=T(n-1)+T(n-3)-T(n-4), n>=4

2.subject 到 T(n)=n 0<=n<=3

Answer 1

我用类似于 C 风格的语言创建了算法。我猜 C# 会运行如果你添加函数 Main 和必需的包含。

int CountT(int n)
{
    if (n < 0)
    {
        throw new Exception("N is lower than zero");
    }
    else if (n <= 3)
    {
        return n;
    }
    else
    {
        return CountT(n-1)+CountT(n-3)-CountT(n-4);
    }
}

Answer 2

通过计算第一个数字，您可以很快怀疑解决方案是 T(n) = n。

然后您可以使用数学归纳法证明这一点：

基础：

对于第一个元素，n = 4，我们可以这样计算值：

T(4) = T(3) + T(1) - T(0) = 3 + 1 - 0 = 4

所以这个说法是正确的。

归纳步骤：

假设T(n) = n，表明T(n+1) = n+1：

T(n+1) = T(n) + T(n-2) - T(n-3) = n + (n-2) - (n-3) = n+1

显示所有 n >= 0 的 T(n) = n。

如何求解递归T(n)=T(n-1)+T(n-3)-T(n-4),n>=4

how to solve the recurrence T(n)=T(n-1)+T(n-3)-T(n-4), n>=4

recurrence