# $T(n/2 +1)$ substitution in recurrence relation

How to find the recurrence relation using domain range substitution method for the below: $$T(n) = 2T\left(\frac{n}{2} +1\right) + n -2$$

I am unable to get a pattern with this relation as it is really confusing. I am guessing the below for $$T(n/2 + 1)$$: $$T\left(\frac{n}{2} +1\right) = 2T\left(\frac{n+2}{4}+1\right)+ \frac{n+2}{2} - 2$$

When I substitute this for $$T(n)$$ it becomes a mess.

Can someone guide me in this please.

Perhaps you can spot the pattern here: \begin{align} T(n) &= 2T\left(\frac{n+2}{2}\right) + n-2 \\ &= 4T\left(\frac{n+6}{4}\right) + 2n-4 \\ &= 8T\left(\frac{n+14}{8}\right) + 3n-6 \\ &= 16T\left(\frac{n+30}{16}\right) + 4n-8 \end{align} More generally, we have $$T(n) = 2^k T\left(\frac{n-2}{2^k} + 2\right) + k(n-2).$$ This implies that $$T(2^k+2) = 2^k T(3) + k2^k.$$

Hint.

Making $$S(n) = T(n+a)$$ we have

$$S(n) = 2T\left(\frac{n+a}{2}+1\right)+n+a-2$$

but

$$T\left(\frac{n+a}{2}+1\right) = S\left(\frac{n+a}{2}+1-a\right) = S\left(\frac n2-\frac a2+1\right)$$

now choosing $$a=2$$ we follow with

$$S(n)=2S\left(\frac n2\right)+n$$

etc.