math - 用特征方程求解递推关系

Question

由于没有看到能够将其输入特征方程的步骤，我在解决这个问题时遇到了一些麻烦。

T(n) = 4T(n-2) +n + n^2 * 2^n; T(0)=0；T(1)=1

我不明白将其转换为 (Rx)(Ry) 形式的步骤。我知道我应该将其转换为 tn - 4T(n-2) - n - n^2 * 2^n = 0 但在这里我迷路了。有人可以给我一个提示（不解决它，我不会从中学到任何东西）

Answer 1

那是因为您无法将其转换为 (Rx)(Ry) 形式。它甚至不是线性关系，所以通常的方法没有帮助。

至于我将如何处理它，您应该注意到T(n)仅取决于T(n-2). 因此偶数和奇数是独立的。因此，请先尝试仅针对偶数索引来解决它。

如果你让T(2k) = F(k)那么你有 F(k) = 4F(k-1) + 4k^2*4^k

希望这足以开始。

Answer 2

要求解一个非齐次（即右手边不为 0）递推关系，您需要求解齐次情况，然后找到一个特解。因此，找到解T(n) - 4T(n-2) = 0，然后利用待定系数的方法来计算通解。