Question

三求解如下递归方程T(n)=5T(n-1)-7T(n-2)+3T(n-3）T0，1，2=1，2，7

Answer 1

为了求解递归方程 $T(n) = 5T(n-1) - 7T(n-2) + 3T(n-3)$，需要先确定它的特征方程，假设 $T(n) = r^n$，将其代入递归方程得到：
$r^n = 5r^{n-1} - 7r^{n-2} + 3r^{n-3}$
整理得到：
$r^3 - 5r^2 + 7r - 3 = 0$
可以将该方程因式分解得到：
$(r-1)(r-1)(r-3) = 0$
因此特征方程的三个根分别为 $r_1 = 1, r_2 = 1, r_3 = 3$。
由于存在重根 $r_1 = r_2 = 1$，因此通解可以写作：
$T(n) = (A + Bn)1^n + Cr_3^n$
其中 $A, B, C$ 是常数，根据初始条件 $T_0 = 1, T_1 = 2, T_2 = 7$ 可以解出：
$A + B = 1$
$A + 2B + 3C = 2$
$A + 4B + 9C = 7$
解得 $A = -1, B = 2, C = 1$，因此通解为：
$T(n) = (-1 + 2n)1^n + 3^ n$
或者简写为：
$T(n) = 2n - 1 + 3^n$