<s>[INST] Homework - Resolve the recurrence relation What's the closed formula of this recurrence relation?
$$a_n = a_{n-1}+2a_{n-2}+2^n \text{ with } a_0=1, a_1=2 $$
 [/INST] A generating function approach would make this straightforward:
$$G(x) = \sum_{n=0}^\infty a_n x^n = 1+2x+\sum_{n=2}^\infty a_n x^n$$
$$=1+2x+\sum_{n=2}^\infty (a_{n-1} + 2a_{n-2} + 2^n)x^n$$
$$=1+2x+\sum_{n=1}^\infty a_n x^{n+1} + 2 \sum_{n=0}^\infty a_n x^{n+2} + \sum_{n=2}^\infty 2^n x^n$$
$$=1+2x+x(G(x)-1)+2x^2G(x)+\frac{2^2x^2}{1-2x}$$
Thus $$G(x)(1-x-2x^2) = 1+x+\frac{2^2x^2}{1-2x}$$ and $$G(x) = \frac{1+x}{1-x-2x^2} + \frac{2^2x^2}{(1-2x)(1-x-2x^2)} = \frac{1+x}{(1+x)(1-2x)} + \frac{2^2x^2}{(1-2x)(1+x)(1-2x)}$$
$$= \frac{1}{(1-2x)} + \frac{2^2x^2}{(1-2x)^2(1+x)}$$
Now you can use partial fractions, and then expand in terms of geometric series to find the taylor coefficients of $G(x)$ which are the terms $a_n$.
</s>