# Converting a Recurrence Relation to its Closed Form

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.