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?
 A: 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$$
A: Let $Sa_n=a_{n+1}$ be the shift operator on sequences. Then your equation becomes
$$
\left(1-S^{-1}\right)^2a_n=2^n+4\tag1
$$
where $1-S^{-1}$ is the backward difference operator.
As with integration, we have a set of basic forms that can be validated by repeated backward difference:
$$
\left(1-S^{-1}\right)^2n^2=2\tag2
$$
$$
\left(1-S^{-1}\right)^22^n=2^{n-2}\tag3
$$
$$
\left(1-S^{-1}\right)^2a_n=0\implies a_n=C_1n+C_2\tag4
$$
looking at $(2)$, $(3)$, and $(4)$, we see that
$$
a_n=2^{n+2}+2n^2+C_1n+C_2\tag5
$$
Plugging in the conditions that $a_0=a_1=0$, we get
$$
a_n=2^{n+2}+2n^2-6n-4\tag6
$$
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}$

$\ds{a_{n} = 2a_{n - 1} - a_{n - 2} + 2^{n} + 4\,,\qquad a_{0} = a_{1} = 0:\ {\large ?}}$.

Note that
$\ds{a_{n} - a_{n - 1} = a_{n - 1} - a_{n - 2} + \pars{2^{n} + 4}}$. Then,
\begin{align}
\underbrace{\sum_{k = 2}^{n}\pars{a_{k} - a_{k - 1}}}
_{\ds{a_{n} - a_{1} = a_{n}}}\ &\ =\
\underbrace{\sum_{k = 2}^{n}\pars{a_{k - 1} - a_{k - 2}}}
_{\ds{a_{n - 1} - a_{0} = a_{n - 1}}}\ +\
\underbrace{\sum_{k = 2}^{n}\pars{2^{k} + 4}}_{\ds{2^{n + 1} + 4n - 8}}
\\[5mm] \implies a_{n} - a_{n - 1} & = 2^{n + 1} + 4n - 8
\end{align}

Similarly,
\begin{align}
\overbrace{\sum_{k = 2}^{n}\pars{a_{k} - a_{k - 1}}}^{\ds{a_{n} - a_{1} = a_{n}}}\ & \ =\
\sum_{k = 2}^{n}\pars{2^{k + 1} + 4k - 8} =
\sum_{k = 1}^{n - 1}\pars{2^{k + 2} + 4k - 4}
\\[5mm] & =
2^{3}\,{2^{n - 1} - 1 \over 2 - 1} + 4\,{\pars{n - 1}n \over 2} - 4\pars{n - 1}
\end{align}

$$
\bbx{a_{n} = 2^{n + 2} + 2n^{2} - 6n - 4\,,\qquad n = 0,1,2,\ldots}
$$
A: 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$.
A: $$\begin{align}
a_{n+2} - 2a_{n+1} + a_{n} &= 4 \cdot 2^{n} + 4 \\
a_{n+1} - 2a_{n} + a_{n-1} &= 2 \cdot 2^{n} + 4 \\
a_{n} - 2a_{n-1} + a_{n-2} &= 1 \cdot 2^{n} + 4 \\
\end{align}$$
$$
\begin{bmatrix}
1 & -2 & 1 & 0 & 0 \\
0 & 1 & -2 & 1 & 0 \\
0 & 0 & 1 & -2 & 1 \\
\end{bmatrix}
\begin{bmatrix} 
a_{n + 2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2}
\end{bmatrix} = 
\begin{bmatrix} 
4 & 1 \\
2 & 1 \\
1 & 1 \\
\end{bmatrix} \begin{bmatrix} 2^n \\ 4 \end{bmatrix}$$
$$
\begin{bmatrix} 1 & -3 & 2 \end{bmatrix}
\begin{bmatrix}
1 & -2 & 1 & 0 & 0 \\
0 & 1 & -2 & 1 & 0 \\
0 & 0 & 1 & -2 & 1 \\
\end{bmatrix}
\begin{bmatrix} 
a_{n + 2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2}
\end{bmatrix} = 
\begin{bmatrix} 1 & -3 & 2 \end{bmatrix}
\begin{bmatrix} 
4 & 1 \\
2 & 1 \\
1 & 1 \\
\end{bmatrix} \begin{bmatrix} 2^n \\ 4 \end{bmatrix}$$
$$
\begin{bmatrix} 1 & -3 & 2 \end{bmatrix}
\begin{bmatrix}
1 & -2 & 1 & 0 & 0 \\
0 & 1 & -2 & 1 & 0 \\
0 & 0 & 1 & -2 & 1 \\
\end{bmatrix}
\begin{bmatrix} 
a_{n + 2} \\ a_{n + 1} \\ a_{n} \\ a_{n - 1} \\ a_{n - 2}
\end{bmatrix} = 
\begin{bmatrix} 0 \end{bmatrix}$$
So the characteristic equation of the linear recursion is
$$(x^2 - 3x + 2)(x^2 - 2x + 1)$$
with roots $[2, 1, 1, 1]$, so the general solution is
$$a_n = C_0 2^n + (C_1 + C_2n + C_3n^2)1^n$$
where the coefficients $C$ can be determined form the initial conditions.
