Solution for t(n)=2t(n-2)-15 , is mine true? [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 12 years ago.

Improve this question

I am not asking for a solution for my homework , i made a solution for this equation and just wanna know whether it is true

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

From these substitutions i concluded that

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

So the solution i reached was

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

BUT the book i am reading : " Algorithms analysis : an active learning approach " used T(2) = 40 and reached another solut开发者_JAVA百科ion

IS MY SOLUTION TRUE TOO ?

Note I am using the direct substitution here not any other method like Master or substitution method

Thanks

---

First of all, your level 1 is wrong, it should be like this:
Level 1
T(n) = 2 * ( 2 * T(n-4) - 15 ) - 15

I would solve it like this:

Since T(1) = T(2) -> T(3) = T(4) -> ... -> T(2k+1) = T(2k+2), where k is a positive integer

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)

This is not a formal proof though.

---

When deriving formulae, one good way of checking is to substitute and check it with a known case.

In this case, substituting 1 results in T(1) = 25*2^((1-1)/2) - 15 = 10, but T(1) should be 40.

Additionally, in the derivation, the level 1 derivation should be 2( 2T(n-4) - 15) - 15 instead of 2( T(n-4) - 15) - 15.