algorithm - Iterative recurrent... 迭代法

Question

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

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

迭代:

i=1

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

i=2

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

i=3

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

i=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。