t(n)=2t(n-2)-15的解，我的是真的吗？

Question

我不是在要求家庭作业的解，而是为这个方程做了一个解，我只想知道它是否是真的。

T(n) = 2 * T(n-2) - 15
T(1) = T(2) = 40

SOLUTION

Level 1
     T(n) = 2 ( T(n-4) -15 ) -15
Level 2
          = 2 ( 2 ( T(n-6) -15 ) -15 ) -15
Level 3
          = 2 ( 2 ( 2 ( T(n-8) -15 ) -15 ) -15 ) -15

通过这些替换，我得出结论：

 T(n) = 2^i [ T(n -2(i+1) ] - (2^(i+1) -1 ) * 15

所以我找到的解决办法是

 T(n) = 25 * 2^[ (n-1)/2 ] -15
 AND I USED T(1) = 40

但我正在读的书“算法分析:主动学习方法”使用了T(2) = 40，并得到了另一种解决方案。

我的解决方案也是真的吗？

备注我在这里使用的是直接替换，而不是像Master或替换方法那样的任何其他方法

谢谢

Answer 1

在推导公式时，一种很好的检验方法是用已知的情况来代替和检验它。

在这种情况下，在T(1) = 25*2^((1-1)/2) - 15 = 10中替换一个结果，但是T(1)应该是40。

此外，在派生过程中，第1级派生应该是2( 2T(n-4) - 15) - 15而不是2( T(n-4) - 15) - 15。

Answer 2

首先，你的1级是错的，应该是这样的：

1级

T(n) = 2 * ( 2 * T(n-4) - 15 ) - 15

我会这样解决的：

既然T(1) = T(2) -> T(3) = T(4) -> . -> T(2k+1) = T(2k+2)，其中k是正整数

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

T(4) = 2*T(2) - 15 = 2*T(1) -1* 15

T(5) = 2*T(3) - 15 = 4*T(1) -3* 15

T(6) = 2*T(4) - 15 = 4*T(1) -3* 15

T(7) = 2*T(5) - 15 = 8*T(1) -7* 15

T(8) = 2*T(6) - 15 = 8*T(1) -7* 15

..。

-> T(2k+1) = (2 ^k* T( 1) ) -(2^ (k - 1) -1)*15

-> T(2k+2) = T(2k+1)

不过，这不是一个正式的证据。