I have a recurrence relation of the form given below (taken from Analysis of Algorithms – An Active Learning Approach by Jeffrey J. McConnell):

$ T(n) = 2T(n – 2) – 15 $

$ T(2) = T(1) = 40 $

I am asked to find a closed-form for the recurrence relation i.e. to remove the recursive nature of the equations.

**Working:** My professor said it would be easier if you could see the patterns taking form if you expand the equations up to a few steps. So,

$ T(n) = 2T(n – 2) – 15 $

$ = 2(2T(n – 4) – 15) – 15$

$ = 4T(n – 4) – 2\times 15 – 15 $

$ = 4(2T(n – 6) – 15) – 2\times15 – 15$

$ = 8T(n – 6) – 4 \times 15 – 2\times15 – 15$

I observe that the coefficient of $ T$ in each step is a power of 2. The size of the problem during each recursive call decreases by 2. Also, there is a -15 term multiplied by the next power of 2.

But I am stuck here and do not know how to proceed further i.e. to obtain a closed-form. The book says to consider cases when $ n$ is odd and even. But I do not get it at all. Any help would be appreciated.

Note: The material hasn’t covered advanced topics like solving recurrence relations yet.