algorithm - 迭代递归...迭代方法

Question

我尝试使用迭代方法解决以下递归关系，

T(1) = 8  
T(n) = 3T(n-1) - 15

迭代：

我=1

T(n) = 3(3T(n-2) - 15) -15

我=2

3(3(3T(n-3) - 15) -15) - 15

我=3

 3(3(3(3T(n-4) - 15) -15) - 15) - 15

我=4

3(3(3(3(3T(n-5) - 15) -15) - 15) - 15) - 15

从迭代模式我发现
T(n) = 3 ⁽ⁱ⁺¹⁾ * T(n-(i+1)) - 15

现在我需要找到这个递归关系的总和并获得封闭形式。我只是不确定如何进行。

有人可以指导我解决这个问题吗？

Answer 1

递归关系是，

T(n) = 3T(n-1) - 15                        ------ 1

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

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

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

对应的特征方程为，

x ² -4x + 3 = 0

x = 3 和 x = 1 是解，

一般的解决方案是，

T(n) = a 1 ⁿ + b 3 ⁿ

这意味着T(n) = a + b 3 ⁿ

我们有 T(1) = 8，

那里为a + 3b = 8 ---- 5

T(2) = 9,

那里为a + 9b = 9 ---- 6

解决 5 和 6，我们得到 a = 15/2 和 b = 1/6。

因此，一般解决方案是T(n) = (1/6) 3 ⁿ + 15/2。