如何求解递归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.以0<=n<=3的T(n)=n为限

Answer 1

通过计算第一个数字，您可以很快怀疑解决方案是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

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

Answer 2

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

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);
    }
}