<s>[INST] Solving Recurrence Relation of $T(n)=4T(n-2)+2$ Question

Solve Recurrence Relation of $T(n)=4T(n-2)+2$
Base case-: $T(1)=1,T(2)=2$

My Approach/solution
$$T(n)=4T(n-2)+2$$
$$T(n-2)=4T(n-4)+2 \tag{1}$$
$$T(n-4)=4T(n-6)+2 \tag{2}$$
Using $(1)$ and $(2)$ in my equation
$$\begin{align*}
T(n)&=4\cdot (4T(n-4)+2)+2\\
&=4^{2}\cdot T(n-2\cdot 2)+2\cdot 4^{1}+2\cdot 4^{0}\\
&=4^{2}\cdot(4T(n-6)+2)+2\cdot 4^{1}+2\cdot 4^{0}\\
&=4^{3}\cdot T(n-2\cdot 3)+2\cdot 4^{2}+2\cdot 4^{1}+2\cdot 4^{0}\\
\vdots \\
&=4^{k}\cdot T(n-2\cdot k)+2\cdot 4^{k-1}+...+2\cdot 4^{2}+2\cdot 4^{1}+2\cdot 4^{0}
\end{align*}$$
Substituing  $T(n-2\cdot k)$ by $2$, i.e $T(2)=2$
$$n-2\cdot k=2 \Rightarrow k=\frac{n-2}{2}$$
So our equation will look like
$$\begin{align*}
T(n)&=2\cdot 4^{k}+2\cdot 4^{k-1}+...+2\cdot 4^{2}+2\cdot 4^{1}+2\cdot 4^{0}\\
T(n)&=2\cdot \left(4^{0}+4^{1}+4^{2}+...+4^{k-1}+4^{k}\right)\\
T(n)&=2\cdot \left(4^{0}\cdot \frac{(4^{k+1}-1)}{4-1}\right)
\end{align*}$$
$k=\frac{n-2}{2}$
$$\begin{align*}
T(n)&=2\cdot \left(\frac{(4^{k+1}-1)}{4-1}\right)\\
T(n)&=2\cdot \frac{2^{n}-1}{3}
\end{align*}$$
Is it correct? Also if it is correct, can anyone hint me another approach as it is bit lengthy.
Thanks!
 [/INST] Using generating functions technique we have 
$$f(x)=\sum\limits_{n=0}T(n)\cdot x^n=T_0+1\cdot x+2\cdot x^2+\sum\limits_{n=3}T(n)\cdot x^n=\\
T_0+1\cdot x+2\cdot x^2+\sum\limits_{n=3}\left(4T(n-2)+2\right)\cdot x^n=\\
T_0+4\sum\limits_{n=3}T(n-2)\cdot x^n + x + 2\cdot x^2 +\sum\limits_{n=3}2\cdot x^n=\\
T_0+4x^2\sum\limits_{n=3}T(n-2)\cdot x^{n-2}-2-x+\sum\limits_{n=0}2\cdot x^n=\\
T_0+4x^2\sum\limits_{n=1}T(n)\cdot x^{n}-2-x+\sum\limits_{n=0}2\cdot x^n=\\
T_0-4T_0x^2-2-x+4x^2\sum\limits_{n=0}T(n)\cdot x^{n}   +\sum\limits_{n=0}2\cdot x^n=\\
T_0-4T_0x^2-2-x+4x^2f(x)+ \frac{2}{1-x}$$
or
$$f(x)=T_0-\frac{2+x}{1-4x^2}+\frac{2}{(1-x)(1-4x^2)}=\\
T_0-\left( \frac{5}{4(1-2x)}+\frac{3}{4(1+2x)} \right)+\left(-\frac{2}{3(1-x)}+\frac{2}{1-2x}+\frac{2}{3(1+2x)} \right)=\\
T_0-\frac{2}{3(1-x)}+\frac{3}{4(1-2x)}-\frac{1}{12(1+2x)}=\\
T_0-\frac{2}{3}\sum\limits_{n=0}x^n+\frac{3}{4}\sum\limits_{n=0}(2x)^n-\frac{1}{12}\sum\limits_{n=0}(-2x)^n=\\
T_0+\frac{2}{3}\sum\limits_{n=0}\left(\frac{3}{4}\cdot 2^n -\frac{1}{12}\cdot (-2)^n-\frac{2}{3}\right)x^n$$
or
$$T(n)=\frac{3}{4}\cdot 2^n -\frac{1}{12}\cdot (-2)^n-\frac{2}{3}, n\geq 1$$
or 
$$T(n)=\frac{1}{12}\left(9\cdot 2^n + (-1)^{n+1}\cdot 2^n-8\right)$$
as presented by Dr. Sonnhard Graubner, only with a complete proof this time. The result is easy to validate $T(1)=1, T(2)=2, T(3)=6$. 
Some of the shortcuts are explained here.
More learning materials here.
</s>