我尝试使用迭代方法解决以下递归关系,
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(i+1) * T(n-(i+1)) - 15
现在我需要找到这个递归关系的总和并获得封闭形式。我只是不确定如何继续。
有人可以指导我解决这个问题吗?
最佳答案
递归关系是,
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
对应的特征方程为,
x2 -4x + 3 = 0
x = 3 和 x = 1 是解,
一般的解决方法是,
T(n) = a 1n + b 3n
这意味着 T(n) = a + b 3n
我们有 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) 3n + 15/2。
关于algorithm - Iterative recurrent... 迭代法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16067681/