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?

Write: 
$$\begin{align}a_n
&=2a_{n-1}-a_{n-2}+2^n+4\\
&=2(2a_{n-2}-a_{n-3}+2^{n-1}+4)-a_{n-2}+2^n+4\\
&=3a_{n-2}-2a_{n-3}+4\cdot2^{n-1}+4(1+2)\\
&=3(2a_{n-3}-a_{n-4}+2^{n-2}+4)-2a_{n-3}+8\cdot2^{n-2}+4(1+2)\\
&=4a_{n-3}-3a_{n-4}+11\cdot2^{n-2}+4(1+2+3)\end{align}$$
You can see a few patterns emerging. 

*

* The coefficient of $a_{n-k}$ is $k+1$

* The coefficient of $a_{n-k-1}$ is $-k$. 

* You end up with an additional term of $4(1+2+...+k)$. 

What about the coefficient of $2^{n-k+1}$? This is $1,4,11,26,57,...$, where at each point, we double and add $k$ to the previous coefficient. This can be written as a separate relation:
$$b_n=2b_{n-1}+n,\,\,\,\,\, b_1=1$$ 
which can be solved just as this one to give 
$$b_n=2^{n+1}-n-2$$
Substituting this in, we get 
$$a_n=(n+2)a_1-(n+1)a_0+[2^n-n-1]2^2+4\cdot\frac12 n(n-1)\\\implies a_n=2^{2+n}+2n^2-6n-4$$ after incorporating the initial conditions $a_0=a_1=0$.
