Use the method of "changing variables" to solve the following recurrence: $T(n) = 2\cdot T(n-2) + n$
I tried doing this, but I don't know how to continue from here. I think it doesn't work and is not correct.

Please help, thanks in advance!
 A: Let $f(x)=T_0+T_1x+T_2x^2+....+T_nx^n+...$. Thus, $x^2f=T_0x^2+T_1x^3+T_2x^4+...+T_{n-2}x^n+....$. Also, note that $\frac{x}{(1-x)^2}=x+2x^2+3x^3+...nx^n+...$
Thus,
$$f-2x^2f-\frac{x}{(1-x)^2}=T_0+(T_1-1)x+(T_2-2T_0-2)x^2+...+(T_n-2T_{n-2}-n)x^n+...$$
$$=T_0+(T_1-1)x$$
Thus,
$$f=\frac{T_0}{1-2x^2}+\frac{x}{(1-2x^2)(1-x)^2}+\frac{(T_1-1)x}{1-2x^2}$$
Now, $\frac{x}{(1-2x^2)(1-x)^2}= \frac{3}{\left(x-1 \right)}+{\frac {-6\,x-4}{2\,{x}^{2}-1}}- \frac{1}{\left( 
x-1 \right) ^{2}}$
Thus atlast we have:
$$f=\frac{T_0+4}{1-2x^2}+\frac{(T_1+5)x}{1-2x^2}+\frac{3}{x-1}-\frac{1}{(x-1)^2}$$
All the above functions are closed forms of well knows geometric series, from which we can find the coefficient of $x^n$ which gives us $T_n$(From the definition of $f$ in the beginning of the answer)
A: $\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,}
 \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$
\begin{align}
\sum_{n = 2}^{\infty}\mrm{T}\pars{n}z^{n} & =
2\sum_{n = 2}^{\infty}\mrm{T}\pars{n - 2}z^{n} + \sum_{n = 2}^{\infty}n\,z^{n}
\\[5mm]
-\,\mrm{T}\pars{0} - \mrm{T}\pars{1}z +
\sum_{n = 0}^{\infty}\mrm{T}\pars{n}z^{n} & =
2z^{2}\sum_{n = 0}^{\infty}\mrm{T}\pars{n}z^{n} +
{\pars{2 - z}z^{2} \over \pars{1 - z}^{2}}
\end{align}

Lets $\ds{\mc{T}\pars{z} \equiv\sum_{n = 0}^{\infty}\mrm{T}\pars{n}z^{n}}$ such
  that $\ds{\mrm{T}\pars{n} = \bracks{z^{n}}\mc{T}\pars{z}}$.

Then,
\begin{align}
\mc{T}\pars{z} & =
{\mrm{T}\pars{0} + \mrm{T}\pars{1}z + \pars{2 - z}z^{2}/\pars{1 - z}^{2} \over
1 - 2z^{2}}
\\[5mm] & =
-\,{1 \over \pars{1 - z}^{2}} - {3 \over 1 - z} +
{\mrm{T}\pars{0} + \mrm{T}\pars{1}z + 4 + 5z \over 1 - 2z^{2}}
\\[5mm] & =
-\sum_{n = 0}^{\infty}{-2 \choose n}\pars{-1}^{n}z^{n} -
3\sum_{n = 0}^{\infty}z^{n} +
\braces{\vphantom{\large A}\mrm{T}\pars{0} + 4 + \bracks{\mrm{T}\pars{1} + 5}z}
\sum_{n = 0}^{\infty}2^{n}z^{2n}
\\[5mm] & =
-\sum_{n = 0}^{\infty}\pars{n + 4}z^{n} +
\sum_{n = 0}^{\infty}\bracks{\mrm{T}\pars{0} + 4}2^{n}z^{2n} +
\sum_{n = 0}^{\infty}\bracks{\mrm{T}\pars{1} + 5}2^{n}z^{2n + 1}
\\[1cm] & =
\sum_{n = 0}^{\infty}\braces{\vphantom{\large A}\bracks{\mrm{T}\pars{0} + 4}\pars{\root{2}}^{2n} - 2n - 4}z^{2n}
\\[2mm] &
+ \sum_{n = 0}^{\infty}\braces{\vphantom{\large A}
{\root{2} \over 2}\bracks{\mrm{T}\pars{1} + 5}\pars{\root{2}}^{2n + 1} - \pars{2n + 1} - 4}z^{2n + 1}
\end{align}

$$
\bbx{\mrm{T}\pars{n} =
\left\{\begin{array}{lcl}
\ds{\bracks{\mrm{T}\pars{0} + 4}2^{n/2} - n - 4} &
\mbox{if} & \ds{n}\ \mbox{is}\ even
\\[2mm]
\ds{\bracks{\mrm{T}\pars{1} + 5}2^{\pars{n - 1}/2} - n - 4} &
\mbox{if} & \ds{n}\ \mbox{is}\ odd
\end{array}\right.}
$$
A: Hint (using "change of variables"):
$$
\begin{align}
T(n) = 2\cdot T(n-2) + n \;\;&\iff\;\; T(n)+n=2\cdot \big(T(n-2)+n-2\big) +4 \\
 &\iff\;\; T(n)+n+4=2\cdot \big(T(n-2)+n-2+4\big)
\end{align}
$$
Let $\,S(n) = T(n)+n+4\,$, then $\,S(n) = 2 \cdot S(n-2)= 2^2 \cdot S(n-4) = 2^3 \cdot S(n-6)= \ldots\,$
