Explicit formula from recursive formula I'm failing to find any reasonable solution to this given problem.
Find explicit formula of $n$-th element from given sequence:
$$\begin{cases}
a_1 = 1\\
a_2 = 2\\
a_{n+2} = 4 a_{n+1} + 4 a_n + 2^n
\end{cases}$$
I have tried finding some clues whilst typing out few first expressions to no avail. I also tried inserting the recursion formula instead of $a_{n+1}$ or $a_n$ though it got very messy in no time and all I have gotten was something like this:
$$a_{n+2} = 4^3 a_{n-3} + \sum\limits_{j=0}^3 (2^{n+j} + 4^{j+1}a_{n-j})$$
Which I believe would get me to:
$$a_{n+2} = 4^{n-1} a_{1} + \sum\limits_{j=0}^{n-1} (2^{n+j} + 4^{j+1}a_{n-j})$$
Any tips on how can I solve this one?
 A: Solving recurrences can be tricky. A systematic approach is to try to solve for the generating function of the sequence and then work from there, but to get the general sequence term from the generating function can also be hard as it involves differentiating $n$ times. This kind of problem is usually solved nicely by a CAS like Mathematica. You can also try to look up the sequence terms in the Online Encyclopedia of Integer Sequences, however for this sequence there doesn't seem to be an entry.
Think about the sequence generating function, that is the formal power series
$$
G(x) = \sum_{n=1}^\infty a_{n+2} x^n
$$
we know the general term for $a_{n+2}$ giving
$$
a_{n+2} = 4 a_{n+1} + 4 a_{n} +2^{n}
$$
Then we know the generating function is
$$
G(x) = \sum_{n=1}^\infty (4 a_{n+1} + 4 a_{n} +2^{n}) x^n \\
G(x) = 4\sum_{n=1}^\infty a_{n+1}x^n + 4\sum_{n=1}^\infty a_{n}x^n +\sum_{n=1}^\infty 2^{n} x^n
$$
consider what these terms mean in relation to our definition of the generating function
$$
G(x) = \sum_{n=1}^\infty a_{n+2} x^n = a_3x^1+a_4x^2+a_5x^3+\cdots\\
4\sum_{n=1}^\infty a_{n+1}x^n =4(a_2x^1+a_3x^2+a_4x^3+\cdots)=4a_2x+4xG(x)\\
4\sum_{n=1}^\infty a_{n}x^n = 4(a_1x^1+a_2x^2+a_3x^3+\cdots)=4a_1x+4a_2x^2+4x^2G(x)
$$
we also know that (when it converges) from the geometric series
$$
\sum_{n=1}^\infty 2^n x^n = \frac{2x}{1-2x}
$$
Altogether we have
$$
G(x) = 8x+4x G(x) + 4x+8x^2+4x^2G(x) + \frac{2x}{1-2x}
$$
$$
G(x)(1-4x-4x^2) = 12x+8x^2 + \frac{2x}{1-2x}\\
G(x) = -\frac{2x(8x^2+8x-7)}{1-6x+4x^2+8x^3} = 14x + 68x^2 + 336x^3 + \cdots
$$
which fits with our original definition. Now we need to extract the sequence of coefficients from this. We can define the full sequence generating function to include the first two terms
$$
g(x) = 1 + 2x + x G(x) = \sum_{n=0}^\infty a_0 x^n = \frac{1-4x+6x^2}{1-6x+4x^2+8x^3}
$$
from this we can differentiate as many times as necessary then set the generating function to zero to get the desired coefficient multiplied by some factor, this can formally be seen as the inverse Z transform of g(1/x).

InverseZTransform[(1-4x+6x^2)/(1-6x+4x^2+8x^3)/.x->1/x,x,n]

Which in Mathematica gives the answer
$$
a_n = -2^{n-2} + \frac{5}{8}(2-2\sqrt{2})^n + 5\cdot2^{n-3}(1+\sqrt{2})^n
$$
which can be seen to recreate the relabelled coefficients $a_0=1, a_1=2, a_3=14, \cdots$. Other ways to get the $n^{th}$ derivative are the Cauchy differentiation formula or by spotting patterns for simple generating functions. 
A: I propose what is possibly a more direct solution. With problems of this type I try to reduce the original recurrence to a more familiar form, usually what I call the generalized Fibonacci form, say, $f_n=af_{n-1}+bf_{n-2}$. In this instance, let us assume that
$$a_n=f_n+A2^n$$
Then,
$$f_{n+2}+A2^{n+2}=4(f_{n+1}+A2^{n+1})+4(f_{n}+A2^{n})+2^{n}$$
Now choose $A$ such that
$$A2^{n+2}=4A2^{n+1}+4A2^{n}+2^{n}\\
\text{or}\\
A=-\frac{1}{8}$$
We are then left with
$$f_{n+2}=4f_{n+1}+4f_{n}$$
with characteristic roots
$$\alpha,\beta=2\pm 2\sqrt{2}$$
The the solution is given by
$$a_n=a\alpha^n+b\beta^n-2^{n-3}$$
where $a,b$ are to be determined from the initial conditions.
