<s>[INST] Show recursion in closed form I've got following sequence formula:
$ a_{n}=2a_{n-1}-a_{n-2}+2^{n}+4$
where $ a_{0}=a_{1}=0$
I know what to do when I deal with sequence in form like this:
$ a_{n}=2a_{n-1}-a_{n-2}$
  -  when there's no other terms but previous terms of the sequence.
Can You tell me how to deal with this type of problems? 
What's the general algorithm behind solving those?
 [/INST] One approach that works to get to the final form is to take the formal power series
$$f(x) = \sum_{n=0}^{\infty} a_n x^n$$
and try and rewrite it in terms of itself. Applying the initial conditions where necessary:
\begin{align}
f(x) &= \sum_{n=0}^{\infty} a_n x^n\\
&= a_0 + a_1 x +\sum_{n=2}^{\infty} \left(2a_{n-1}-a_{n-2} + 2^n + 4\right) x^n\\
%
&= 2\sum_{n=2}^{\infty}a_{n-1}x^n - \sum_{n=2}^{\infty}a_{n-2}x^n + \sum_{n=2}^{\infty}2^nx^n + 4\sum_{n=2}^{\infty}x^n\\
%
&= 2\sum_{n=1}^{\infty}a_nx^{n+1} - \sum_{n=0}^{\infty}a_n x^{n+2} + \sum_{n=0}^{\infty}(2x)^{n+2} + 4\sum_{n=0}^{\infty}x^{n+2}\\
%
&= 2x\left(\sum_{n=0}^{\infty}a_nx^n - a_0\right) - x^2\sum_{n=0}^{\infty}a_n x^n + 4x^2\sum_{n=0}^{\infty}(2x)^n + 4x^2\sum_{n=0}^{\infty}x^n\\
%
&= 2xf(x) - x^2f(x) + 4x^2 \frac{1}{1-2x} + 4x^2 \frac{1}{1-x}\\
%
&= (2x-x^2)f(x) + 4x^2\frac{(1-x)+(1-2x)}{(1-2x)(1-x)}\\
%
&= (2x-x^2)f(x) + \frac{4x^2(2-3x)}{(1-2x)(1-x)}
\end{align}
Solving for $f(x)$:
$$f(x) = \frac{4x^2(2-3x)}{(1-2x)(1-x)(1-2x+x^2)} = \frac{4x^2(2-3x)}{(1-2x)(1-x)^3}$$
Applying partial fraction expansion and using the well-known result that 
$$\sum_{n=0}^{\infty} (n+1)(n+2)\dotsb(n+m)x^n
= \frac{d^m}{dx^m}\left(\frac{1}{1-x}\right)
= \frac{m!}{(1-x)^{m+1}}$$
we get
\begin{align}
\sum_{n=0}^{\infty} a_n x^n &=
\frac{4x^2(2-3x)}{(1-2x)(1-x)^3}\\
&= \frac{4}{1-2x} + \frac{4}{1-x} - \frac{12}{(1-x)^2} + \frac{4}{(1-x)^3}\\
&= 4\frac{1}{1-2x} + 4\frac{1}{1-x} - 12\frac{1!}{(1-x)^{1+1}} + 2 \frac{2!}{(1-x)^{2+1}}\\
&= 4 \sum_{n=0}^{\infty} (2x)^n + 4 \sum_{n=0}^{\infty} x^n - 12 \sum_{n=0}^{\infty} (n+1) x^n + 2 \sum_{n=0}^{\infty} (n+1)(n+2) x^n\\
&= \sum_{n=0}^{\infty} \left(4\cdot 2^n + 4 - 12(n+1) + 2(n+1)(n+2)\right)x^n\\
&= \sum_{n=0}^{\infty} \left(2^{n+2} + 2n^2 - 6n -4\right)x^n
\end{align}
Equating coefficients, we find
$$a_n = 2^{n+2} + 2n^2 - 6n -4$$
</s>